If the cycle begins with ai,cio, then the ladder is descended in an order where tiie с at a level precedes the b as;

A crucial point in the proof is that we can treat the first order, where descent is from es to lower bs as if the variable corresponding to the gadget is made true, while the order in whicli descent is from bs to the lower es corresponds to making that variable false.

After traversing the gadget Hi, the cycle must go to a, where there is another choice; go to bzo or C2o next. However, as we argued for Я], once we make a choice of whether to go left or right from 02, the path through H2 is fixed. In general, when we enter each Hi we have a choice of going left or right, but no other choices if we are not to render a node inaccessible (i.e., the node cannot appear on a directed Hamilton circuit, because all of its predecessors have appeared already).

In what follows, it helps to think of making the choice of going from aj to fejo as making variable Xi true, while choosing to go from Oj to do is tantamount to making Xi false. Thus, the graph of Fig. 10.9(b) has exactly 2 directed Hamilton circuits, corresponding to the 2 truth assignments to n variables.

However, Fig. 10.9(b) is only the skeleton of the graph that we generate for 3-CNF expression E. For each clause ej, we introduce another subgraph Ij, shown in Fig. 10.9(c). Gadget Ij has the property that if a cycle enters at tj, it must leave at uj; if it enters at Sj it must leave at Vj, and if it enters at t.j it must leave at Wj. The argument we shall oifer is that if the cycle, once it reaches Ij, does anything but leave by the node below the one in which it entered, th(;ii one or more nodes are inaccessible - they can never appear on the cycle. By symmetry, we can consider only the case where rj is the first nod(; of Ij on the cycle. There are three cases;

1. The next two vertices on the cycle are Sj and tj. If the cycle then goes to Wj and leaves, Vj is inaccessible. If the cycle goes to Wj and Vj and then leaves, itj is inaccessible. Thus, the cycle must leave at Uj, having traversed all six nodes of the gadget.

2. The next two vertices after rj are Sj and Vj. If the cycle does not next go to Uj, then Uj becomes inaccessible. If after Uj, the cycle next goes to Wj, then tj can never appear on the cycle. The argument is the reverse of the inaccessibility argument. Now, tj can be reached from outside, but if the cjcle later includes tj, there will be no next node possible, because both successors of tj appeared earlier on the cycle. Thus, in this case also, the cycle leaves by Uj. Note, however, that tj and Wj are left untraversed; they will have to appear later on the cycle, which is possible.

3. The circuit goes from rj directly to Uj. If the cycle then goes to Wj, then tj cannot appear on the cycle because its successors have both appeared previously, as we argued in case (2). Thus, in this case, the cycle must

leave directly by Uj, leaving the other four nodes to be added to the cycle later.

To complete the construction of the graph G for expression E, we connect the Ijs to the Hi в as follows: Suppose the first literal in clause ej is ij, an unnegated variable. Pick some node cip, for p in the range 0 to тп - 1, that has not yet been used for the purpose of connecting to one of the / gadgets. Introduce arcs from cip to Vj and from Uj to hp+i. Lf the first literal of clause ej is Щ, a negated literal, then find an unused bjp. Connect bip to Tj and connect

Uj to Ci,p-(-] .

For the second and third literals of e, we make the same additions to the graph, with one exception. For the second Hteral, we use nodes Sj and Vj, and for the third literal we use nodes tj and Wj. Thus, each Ij has three connections to the H gadgets that represent the variables involved in the clause ej. The connection comes from a c-node and returns to the b-node below if the literal is unnegated, and it comes from a b-node, returning to the c-node below, if the literal is negated. We claim that:

The graph G so constructed has a directed Hamilton circuit if and only if the expression E is satisfiable.

(If) Suppose there is a satisfying truth assignment T for E. Construct a directed Hamilton circuit as follows.

1. Begin with the path that traverses only the Hs [i.e., the graph of Fig, 10.9(b)] according to the truth assignment T. That is, the cycle goes from fli to ho if r(a;i) = 1, and it goes from щ to сш if T(a;i) = 0.

2. However, if the cycle constructed so far follows an arc from bjp to Cjp+i, and bip has another arc to one of the s that has not yet been included in the cycle, introduce a detour in the cycle that includes all six nodes of Ij on the cycle, returning to Ci,p+i. The arc bip Cj.p-n will no longer be on the cycle, but the nodes at its ends remain on the cycle.

3. Likewise, if the cycle has an arc from c,p to bj-.p+i, and Cjp has another arc out that goes to an Ij that has not yet been incorporated into the cycle, modify the cycle to detour through all six nodes of Ij.

The fact that T satisfies E assures us that the original path constructed by step (1) will include at least one arc that, in step (2) or (3), allows us to include the gadget Ij for each clause ej. Thus, all the Ijs get included in the cycle, which becomes a directed Hamilton circuit.

(Only-if) Now, suppose that the graph G has a directed Hamilton circuit, we must show that E is satisfiable. First, recall two important points from the analysis we have done so far:

1. If a Hamilton circuit enters some Ij at t-j, ,Sj, or ij, then it must leave at Uj, Vj, or Wj, respectively.

Example 10.22: Let us give a very simple example of the construction of Theorem 10.21, based on the 3-CNF expression E = {х1+Х2+хз){х+Х2+ха). The constructed graph is shown in Fig. 10.10. Arcs that connect Я-type gadgets to /-type gadgets are shown dotted, to improve readabihty, but there is no other distinction between dotted and solid arcs.

For instance, at the top left, we see the gadget for xi. Since xi appears once negated and once unnegated, the ladder needs only one step, so there are two rows of bs and es. At the bottom left, we see the gadget for xg, which appears twice unnegated and does not appear negated. Thus, we need two different сзр -) arcs that we can use to attach the gadgets for h and h

to represent uses of xs in these clauses. That is why the gadget for хз needs three b~c rows.

Let us consider the gadget h, whicli corresponds to the clause {х{+Х2 + хз). For the first Uteral, xT, we attach бю to га and we attach U2 to сц. For the second hteral, SJ, we do the same with 20, S2, э, and c21. The third literal, being unnegated, is attached to a с and the b below; that is, we attach с3) to t2 and W2 to Ьз2.

One of several satisfying truth assignments is xi = 1; 12 - 0, and 2:3 = 0. For this assignment, the first clause is satisfied by its first literal x-\, while the second clause is satisfied by the second literal, X2. For this truth assignment, we can devise a Hamilton circuit in which the arcs Oi b\o, Ua C2o, and аз С30 are present. The cycle covers the first clause by detouring from H\ to Ii \ i.e., it uses the arc сю г\, traverses all the nodes of Д, and returns to йц. The second clause is covered by the detour from Я2 to h starting with the arc 20 S2, traversing all of /2, and returning to C21 The entire hamilton cycle is shown with thicker fines (solid or dotted) and very large arrows, in Fig. 10.10. □

2. Thus, if we view the Hamilton circuit as moving through the cycle of H gadgets, as in Fig. 10.9(b), the excursions that the path makes to some Ij can be viewed as if the cycle followed an arc that was in parallel with one of the arcs bip Cip+i or Cip -> bip+i.

If we ignore the excursions to the Ijs, then the Hamilton circuit must be one of the 2 cycles that axe possible using the Яз ordy - those that make choices to move from each щ to either or Cia. Each of these choices corresponds to a truth assignment for the variables of E. If one of these choices yields a Hamilton circuit including the /js, then this truth assignment must satisfy E.

The reason is that if the cycle goes from to Ьщ, then we can only make an excursion to Ij if the jth clause has xi as one of its three literals. If the cycle goes from щ to c,o, then we can only make an excursion to Ij if the jth clause has x7 as a hterab Thus, the fact that all Ij gadgets can be included implies that the truth assignment makes at least one of the three literals of each clause true; i.e., E is satisfiable. □