Graph Puzzles - Study Note

Graph Puzzles Contents 1 Graph puzzles 1.1 1.2 1.3 1.4 1.5 1.6 The 15 Puzzle . . . . . . A Graph Puzzle . . . . . Preliminaries . . . . . . . Lemmas . . . . . . . . . Proof of the Main Lemma The 15-puzzle redux . . . 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 .8 .9 12 16 18 Bibliography 21 Index 23 3 1 Graph puzzles 1.1 The 15 Puzzle The well-known 15-puzzle consists of 15 sliding squares in a 4 × 4 grid. The object is typically to return a scrambled puzzle to the configuration shown below, or to produce some other specified pattern from this configuration. A legal move in the puzzle consists of sliding a square into the blank spot. You can play the game here. Viewed as a permuation of 16 items (the 15 squares plus the blank spot), this is the transposition of the blank with another item. If the blank spot is returned to the bottom right corner after a series of such moves, the number of moves must be even, and hence any pattern produced in this way must be an even permutation. For example, we cannot produce the pattern in which the 14 and 15 squares are interchanged and all other squares remain in their original places, since that is an odd permutation. This leaves open the 5 6 Chapter 1 Graph puzzles question of whether all even permutations can be produced by a sequence of legal moves; as we will show, the answer is yes. Our proof is essentially that of Aaron Archer [1]. We begin by relabeling the puzzle pieces for convenience: 4 3 2 1 5 6 7 8 12 11 10 9 13 14 15 . The new numbering follows the path shown by dashed lines. We now want to show that all even permutations of this starting configuration can be achieved. We define nine simple permutations that can be achieved as follows: for each, swap the blank along the dashed path until arriving at one of the squares 6, 8, 10, 12, 14, 16 (the bottom right square, that is, the blank doesn’t move at all). Now swap the blank up, then swap it along the dashed path back to its original position. For example, if we stop at square 12 we get this: 4 3 2 1 5 6 7 8 11 10 9 4 5 3 2 1 4 3 2 1 6 7 8 6 7 8 9 11 10 9 12 5 11 10 12 13 14 15 12 13 14 15 13 14 15 . . . In this permuation, 1 through 4 and 12 through 15 are in their original positions. The permutation is a single odd cycle, (11, 10, 9, 8, 7, 6, 5). In the same way we produce 5 other cycles: p1 = (5, 4, 3) p2 = (7, 6, 5, 4, 3, 2, 1) p3 = (9, 8, 7) p4 = (11, 10, 9, 8, 7, 6, 5) p5 = (13, 12, 11) p6 = (15, 14, 13, 12, 11, 10, 9) 1.1 Now we note that The 15 Puzzle 7 p22 p21 p−2 2 = (1, 2, 3) p12 p21 p−1 2 = (2, 3, 4) p21 = (3, 4, 5) 2 1 p−1 2 p1 p3 = (4, 5, 6) p24 p23 p−2 4 = (5, 6, 7) p14 p23 p−1 4 = (6, 7, 8) p23 = (7, 8, 9) 2 1 p−1 4 p3 p4 = (8, 9, 10) p26 p25 p−2 6 = (9, 10, 11) p16 p25 p−1 6 = (10, 11, 12) p25 = (11, 12, 13) 2 1 p−1 6 p5 p6 = (12, 13, 14) 2 2 p−2 6 p5 p6 = (13, 14, 15) Thus, we can produce any 3-cycle of the form (i, i + 1, i + 2). Now a lemma and a theorem will finish things off. LEMMA 1.1.1 in Sn . The 3-cycles of the form (i, i + 1, i + 2) in Sn generate all of the 3-cycles Proof. The proof is by induction on n. The base case is n = 3. S3 contains just two 3-cycles, (1, 2, 3) and (1, 3, 2). Since (1, 3, 2) = (1, 2, 3)2 , we’re done. Now suppose n ≥ 4. We have 3-cycles (1, 2, 3), (2, 3, 4), . . . , (n − 3, n − 2, n − 1), (n − 2, n − 1, n). By the induction hypothesis, (1, 2, 3), (2, 3, 4), . . . , (n − 3, n − 2, n − 1) generates all 3-cycles in Sn−1 . Also by the induction hypothesis, the cycles (2, 3, 4), . . . , (n − 3, n − 2, n − 1), (n − 2, n − 1, n) generate all 3-cycles in the symmetric group on the elements {2, 3, . . . , n}. Thus, we can generate all 3-cycles except possibly a 3-cycle of the form (1, x, n) or (1, n, x) = (1, x, n)2 . Of course, if we can generate the former we can generate the latter. Let y ∈ / {1, x, n}. We know we can generate (1, x, y) and (x, y, n); then (1, x, y)(y, x, n) = (1, x, n). This finishes the proof. THEOREM 1.1.2 The 3-cycles in Sn generate An . Proof. Suppose σ ∈ An , so σ is a product of an even number of transpositions: σ = (a1 , b1 )(a2 , b2 ) · · · (ak , bk ), with k even. Consider an adjacent pair (ai−1 , bi−1 )(ai , bi ) = (a, b)(c, d) with i even. If {a, b} = {c, d} then (a, b)(c, d) is the identity and trivially a 8 Chapter 1 Graph puzzles product of 3-cycles. If a = d and a, b, c are distinct, then (a, b)(c, a) = (a, c, b). Finally, if a, b, c, d are distinct, (a, b)(c, d) = (a, b, c)(b, c, d). Thus σ is a product of 3-cycles. Putting these results together with the fact that all 3-cycles of the form (i, i + 1, i + 2) can be realized in the 15 puzzle, we see that all even permutations can be realized. 1.2 A Graph Puzzle We now generalize the puzzle. Suppose G is a simple graph on n + 1 vertices, and that the vertices have been labeled with [n] = {1, 2, 3, . . . , n}, leaving one vertex v unlabeled. A legal move is to slide a label from a neighbor w of v to v. The goal is to produce a particular lableling from a given initial labeling. For example, if G is the labeled graph below, we have the 15-puzzle. 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 . • 14 • 15 • Figure 1.2.1 • The 15-puzzle as a graph puzzle. More formally, a labeling is a bijection f : V (G) → [n] ∪ {∅}. Two labelings f and g are adjacent if either may be obtained from the other by a legal move; that is, if f (v) = ∅, and w is a neighbor of v, g = f ◦ (v, w) = f (v, w), where (v, w) is the bijection transposing v and w. (We will generally leave out the composition operator “◦”.) Thus g(v) = f (w), g(w) = f (v) = ∅, and otherwise g(x) = f (x). We define a new simple graph puz(G) as follows: the vertex set V (puz(G)) contains all labelings of G, and two labelings are adjacent in puz(G) if and only if they are adjacent as defined in the previous paragraph. Now given initial labeling f and goal labeling g, the question we want to answer is: Are f and g in the same connected component of puz(G)? Our principal result will be that for almost all 2-connected graphs G, puz(G) has one or two connected components, and when there are two, we provide an easy way to determine when f and g are in the same component. The proof is due to R. M. Wilson [2]. 1.3 Preliminaries 9 Exercises 1.2. 1. Prove that from the “standard” position shown in figure 1.2.1 it is not possible to produce the position shown below. 1.3 15 • 14 • 13 • 12 • 11 • 10 • 9 • 8 • 7 • 6 • 5 • 4 • 3 •. 2 • 1 • • Preliminaries A path in a graph G is a sequence p = (v0 , . . . , vk ) of vertices such that vi is adjacent to vi+1 ; the length of the path is k. It is a simple path if the vertices are distinct, or if {v0 , . . . , vk−1 } are distinct and vk = v0 , in which case it is a simple closed path. We denote the path (vk , . . . , v0 ) by p, the reverse of p. Given path p, define a permutation σp : V (G) → V (G) by σp = (vk , vk−1 ) · · · (v2 , v1 )(v1 , v0 ) = (vk , vk−1 , . . . , v1 , v0 ). PROPOSITION 1.3.1 Labelings f and g of G are in the same component of puz(G) if and only if f = gσp for some path p from f −1 (∅) to g −1 (∅). Proof. Given f = g(g −1 (∅), vk−1 )(vk−1 , vk−2 ) · · · (v1 , f −1 (∅)), let hi = g(g −1 (∅), vk−1 ) . . . (vi+1 , vi ), so that g hk−1 = g(g −1 (∅), vk−1 ), hk−2 = hk−1 (vk−1 , vk−2 ), .. . h1 = h2 (v2 , v1 ), f = h1 (v1 , f −1 (∅)) is a path from g to f in puz(G). 10 Chapter 1 Graph puzzles If f and g are in the same component, then there are permutations h1 , . . . , hk−1 such that hk−1 = g(g −1 (∅), vk−1 ), hk−2 = hk−1 (vk−1 , vk−2 ),. . . , h1 = h2 (v2 , v1 ), f = h1 (v1 , f −1 (∅)). Thus, with p = (f −1 (∅), v1 , v2 , . . . , vk−1 , g −1 (∅)), f = gσp . DEFINITION 1.3.2 Let Γ(v, w) = ΓG (v, w) be the set of all permutations σp where p is a path from v to w. We use Γ(v) = ΓG (v) to denote Γ(v, v). DEFINITION 1.3.3 If p is a path from u to v, and q is a path from v to w, we denote by pq the path from u to w consisting of p followed by q. The following lemma is easy. LEMMA 1.3.4 σq σp = σpq ; σp−1 = σp . PROPOSITION 1.3.5 For all v of G, Γ(v) is a group of permutations, all of which fix v. If p is a path from v to w, then Γ(v, w) = σp Γ(v) = Γ(w)σp , and consequently Γ(w) = σp Γ(v)σp−1 . Proof. It is easy to check that Γ(v) is a group. Suppose q is a path from v to w. Then σq = σp σp σq , and since σp σq = σqp ∈ Γ(v), Γ(v, w) ⊆ σp Γ(v). Suppose q is a path from v to v. Then σp σq = σqp ∈ Γ(v, w), so Γ(v, w) ⊇ σp Γ(v). Thus Γ(v, w) = σp Γ(v). The proof that Γ(v, w) = Γ(w)σp is essentially identical. Recall that the symmetric group on a set X = {x1 , . . . , xn } is the group of all permutations of X, which we denote S(X), and the alternating group on X is the set of all even permutations on X, denoted A(X). Of particular interest will be the theta graphs, or θ-graphs. A θ-graph consists of a cycle plus an additional path whose endpoints are two distinct vertices, say v and w, of the cycle. The graph thus consists of three internally disjoint paths from v to w, with a, b, and c internal vertices. We will say this is the θ-graph of type (a, b, c), and without loss of generality, we usually ensure a ≥ b ≥ c. We will need to single out a particular θ-graph, θ0 , of type (2, 2, 1): • • • •. • • • Most of our effort will be in proving the following lemma. 1.3 Preliminaries 11 LEMMA 1.3.6 Let G be a simple 2-connected graph on n vertices, other than a cycle or the graph θ0 . Then, for any vertex v of G, Γ(v) is the symmetric group on V (G)\{v}, unless G is bipartite, in which case Γ(v) is the alternating group on V (G)\{v}. Our principal theorem is THEOREM 1.3.7 Let G be a simple 2-connected graph on n vertices, other than a cycle or the graph θ0 . Then puz(G) is connected unless G is bipartite. If G is bipartite, puz(G) has exactly two components, and if labelings f and g have unoccupied vertices at distance d from each other, then f and g are in the same component if and only if g −1 f is a permutation of V (G) with the same parity as d. Proof. Let G be a simple 2-connected graph and v a vertex of G. Each component of puz(G) contains an f with f (v) = ∅. Labelings f and g, with g(v) = ∅, are in the same component if and only if f = gσp , where p is a path from v to v. That is, f and g are in the same component if and only if g −1 f ∈ Γ(v). Fix a labeling h with h(v) = ∅. For any labeling g, let τg = h−1 g. The map g 7→ τg is a bijection from the set of labelings that map v to ∅ to S(V (G)\{v}). Now we have g −1 f ∈ Γ(v) if and only if (hτg )−1 hτf ∈ Γ(v) if and only if τg−1 τf ∈ Γ(v) if and only if τf Γ(v) = τg Γ(v). Thus, the components of puz(G) are in 1–1 correspondence with the cosets of Γ(v) in S(V (G)\{v}). By lemma 1.3.6, Γ(v) is either S(V (G)\{v}) or A(V (G)\{v}). If the former, there is one coset and hence puz(G) is connected. If Γ(v) = A(V (G)\{v}), suppose that f (v) = g(w) = ∅, and let p be a path from v to w. Then f and g are in the same component if and only if g −1 f ∈ Γ(v, w) = σp Γ(v) if and only if g −1 f and σp have the same parity if and only if g −1 f and the length of p have the same parity. The proof of lemma 1.3.6 is by induction. By proposition 1.3.5, it suffices to prove the lemma for a single v. Also, it will suffice to show that A(V (G)\{v}) ⊆ Γ(v), since Γ(v) contains an odd permutation if and only if G contains an odd length closed path if and only if G is not bipartite. Exercises 1.3. 1. Prove lemma 1.3.4. 2. Prove that Γ(v) is a group, as claimed in proposition 1.3.5. 3. Let G be a cycle on n ≥ 3 vertices. How many components are in puz(G)? What is Γ(v)? 12 1.4 Chapter 1 Graph puzzles Lemmas LEMMA 1.4.1 Let X be a finite set, |X| ≥ 3, x, y ∈ X. Then the 3-cycles C = {(x, y, z)|z ∈ X\{x, y}} generate A(X). Proof. A 3-cycle is an even permutation, so the group G generated by C is contained in A(X). Suppose σ ∈ G, so σ is a product of an even number of transpositions. Any transposition (a, b) can be written (a, b) = (y, a)(y, b)(y, a), so σ can be written as σ = (y, a1 )(y, a2 ) · · · (y, am ), m even, and hence σ = (y, a2 , a1 )(y, a4 , a3 ) · · · (y, am , am−1 ), since (y, a)(y, b) = (y, b, a). If a2i−1 = x, (y, a2i , a2i−1 ) = (x, y, a2i ). Otherwise, (y, a2i , a2i−1 ) = (x, y, a2i )(x, y, a2i−1 )(x, y, a2i )−1 . Thus, σ can be written as a product of 3-cycles of the form (x, y, z) and (x, y, z)−1 , so A(X) ⊆ G. DEFINITION 1.4.2 x}. If σ ∈ S(X), the support of σ, denoted ∥σ∥, is {x ∈ X|σ(x) ̸= DEFINITION 1.4.3 A subgroup H ≤ S(X) is transitive on X if for all x, y ∈ X there is a σ ∈ H such that σ(x) = y. DEFINITION 1.4.4 LEMMA 1.4.5 equivalent. If Σ ⊆ S(X), ⟨Σ⟩ is the subgroup of S(X) generated by Σ. Suppose Σ is a set of 3-cycles in S(X), |X| ≥ 3. Then the following are 1. ⟨Σ⟩ = A(X) 2. ⟨Σ⟩ is transitive on X. Proof. If H ≤ S(X) and Y ⊆ X, let H|Y = {σ ∈ H|∥σ∥ ⊆ Y }. H|Y is a subgroup of S(X) but we interpret it as a subgroup of S(Y ). It is easy to see that (1) implies (2). Suppose that Σ has property 2. Let Y ⊆ X such that |Y | ≥ 3, ⟨Σ⟩|Y = A(Y ), and Y is maximal with these properties. We show that Y = X, which finishes the proof. There is a set Y with the first two properties: Let σ = (a, b, c) ∈ Σ, and let Y = {a, b, c}. Then ⟨Σ⟩|Y = {e, (a, b, c), (a, c, b)} = A(Y ). Now let Y be a maximal set with these properties, and suppose that Y ̸= X. Since Σ has property 2, ⟨Σ⟩ contains a permutation σ that maps an element of Y to an element of X\Y . Therefore, Σ contains a 3-cycle that maps an element of Y to an element of X\Y . This 3-cycle has one of two forms: (x, y, z) with x, y ∈ Y and z ∈ / Y , or (x, y, z) with z ∈ Y and x, y ∈ / Y. 1.4 Lemmas 13 In the first case, since ⟨Σ⟩|Y = A(Y ), ⟨Σ⟩ contains all 3-cycles (x, y, t), t ∈ Y . Thus ⟨Σ⟩ contains all 3-cycles (x, y, t), t ∈ Y ∪ {z}. By lemma 1.4.1, ⟨Σ⟩|Y ∪{z} = A(Y ∪ {z}) contradicting the maximality of Y . In the second case, for each t ∈ Y , ⟨Σ⟩|Y contains a permutation σ such that σ(z) = t, because ⟨Σ⟩|Y = A(Y ). Hence σ(xyz)σ −1 = (xyt) ∈ ⟨Σ⟩. Since this is true for every t ∈ Y , ⟨Σ⟩|Y ∪{x,y} = A(Y ∪ {x, y}), again by lemma 1.4.1, which is again a contradiction. DEFINITION 1.4.6 A permutation group G on X, |X| ≥ 3 is primitive if it preserves no non-trivial partition of X. (The single set X and the collection of all singleton subsets are the trivial partitions. G preserves a partition if every σ ∈ G induces a permutation of the sets of the partition.) DEFINITION 1.4.7 A permutation group G on X is doubly transitive if it is transitive and for every x, y, z ∈ X, with x ∈ / {y, z}, there is a σ ∈ G such that σ(x) = x and σ(y) = z. It is easy to see that if G is doubly transitive then it is primitive. LEMMA 1.4.8 Suppose G is a primitive transitive permutation group on X, and G contains a 3-cycle. Then A(X) ⊆ G. Proof. Let Σ be the set of 3-cycles in G. We claim that G preserves the orbits of ⟨Σ⟩. First, we show that ⟨Σ⟩ ◁ G. Suppose σ ∈ ⟨Σ⟩, that is, σ is a product of 3-cycles. Let τ ∈ G; we need to show that τ στ −1 ∈ ⟨Σ⟩. Write τ στ −1 = τ c1 c2 c3 · · · ck τ −1 = τ c1 τ τ −1 c2 τ τ −1 c3 τ τ −1 · · · τ τ −1 ck τ −1 , where the ci are 3-cycles. Now it suffices to show that τ ci τ −1 is a 3-cycle. It is easy to verify that τ (a, b, c)τ −1 = (τ (a), τ (b), τ (c)). Now suppose that τ ∈ G, that X1 and X2 are orbits of ⟨Σ⟩, that x ∈ X1 , and that τ (x) ∈ X2 . We need to show that τ (X1 ) = X2 . Suppose that y ∈ X1 , so there is a σ ∈ ⟨Σ⟩ such that σ(x) = y. Then τ (y) = τ στ −1 (τ (x)). Since τ στ −1 ∈ ⟨Σ⟩, τ (y) ∈ X2 , so τ (X1 ) ⊆ X2 . If z ∈ X2 , there is a σ ∈ ⟨Σ⟩ such that στ (x) = z. Then z = στ (x) = τ (τ −1 στ (x)), and since τ −1 στ ∈ ⟨Σ⟩, τ −1 στ (x) ∈ X1 , and so z ∈ τ (X1 ). Thus, τ (X1 ) ⊇ X2 . Since G is primitive and preserves the orbits of ⟨Σ⟩, the orbits must form a trivial partition of X. Since ⟨Σ⟩ contains a 3-cycle, the orbits cannot be the singletons, so there must be a single orbit, all of X. Thus, ⟨Σ⟩ is transitive and by lemma 1.4.5, A(X) = ⟨Σ⟩ ⊆ G. 14 Chapter 1 Graph puzzles LEMMA 1.4.9 Let X = {y, a1 , a2 , . . . , an , z, b1 , b2 , . . . , bm }, n ≥ m ≥ 0, and let π = (a1 , a2 , . . . , an , z, b1 , b2 , . . . , bm ) ρ = (b1 , b2 , . . . , bm , y, a1 , a2 , . . . , an ). Then ⟨π, ρ⟩ = S(X) if n + m is odd and ⟨π, ρ⟩ = A(X) if n + m is even, unless 1. n = 2, m = 1, 2. n = m = 2, or 3. n = 4, m = 2. Proof. Without loss of generality, we may assume n ≥ m. It suffices to show that A(X) ⊆ ⟨π, ρ⟩, since π and ρ have the same parity as m + n. The group ⟨π, ρ⟩ is doubly transitive on X: it is clearly transitive on X, and it is then not hard, but somewhat tedious, to see that it is doubly transitive. For example, suppose we seek a σ that fixes ai and such that σ(bk ) = aj , i ̸= j. First, note that π n−i+1 (ai ) = z and π n−i+1 (bk ) = x, where x ∈ {a1 , . . . , an , b1 , . . . , bm }. Then there is a p such that ρp (x) = π n−i+1 (aj ) ∈ {a1 , . . . , an , b1 , . . . , bm }. Now π i−n−1 ◦ ρp ◦ π n−i+1 fixes ai and maps bk to aj . If n = m = 0, ⟨π, ρ⟩ = {()} = A({y, z}. Otherwise, by lemma 1.4.8, it suffices to show that ⟨π, ρ⟩ contains a 3-cycle. Suppose first that n ≥ m ≥ 3. Then ⟨π, ρ⟩ contains the following permutations: σ1 = ρπ −1 = (y, a1 )(z, b1 ) σ2 = πσ1 π −1 = (y, a2 , b1 , b2 ) σ3 = πσ2 π −1 = (y, a3 , b2 , b3 ) σ4 = ρ−m σ1 ρm = (b1 , b2 )(z, ak+1 ), k = n − m ≤ n − 3 σ5 = σ2 σ4 σ6 = πσ5 π −1 σ7 = ρ1−m σ1 ρm−1 σ8 = σ7 σ3 = (y, a3 )(z, ak+2 ) σ9 = σ8 σ6 = (z, ak + 2, b1 ). Next, suppose n > m ≥ 0, n ̸= 2m, m < 3. If m = 0, ρπ −1 = (a1 , z, y). If m > 0, τ1 = ρπ −1 = (y, a1 )(z, b1 ) τ2 = ρm τ1 ρ−m = (am , am+1 )(zy) τ3 = π 2m τ1 π −2m = (y, c)(am , am+1 ), where c = π 2m (a1 ) ∈ / {y, z, am , am+1 }. Then τ3 τ2 = (y, z, c). 1.4 Lemmas 15 The only remaining case is n = m = 1, in which case π and ρ are 3-cycles. In fact, in the three excluded cases of the lemma, the lemma is false, but we will not prove this. Wilson ([2]) does compute ⟨π, ρ⟩ in these cases. LEMMA 1.4.10 The Handle Theorem Suppose G is 2-connected and K is a 2connected proper subgraph of G. Then there are subgraphs H and A (the handle) of G such that H is 2-connected, H contains K, A is a simple path, H and A share exactly the endpoints of A, and G is the union of H and A. Proof. Given G and K, let H be a maximal 2-connected proper subgraph of G containing K. If V (H) = V (G), let e be an edge not in H. Since H plus the edge e is 2-connected, it must be G, by the maximality of H. Hence A is the path consisting of e and its endpoints. Suppose that v is in V (G) but not V (H). Let u be a vertex of H. Since G is 2connected, there is a cycle C containing v and u. Following this cycle from v to u, Let w be the first vertex in H. Continuing on the cycle from u to v, let x be the last vertex in H. If x ̸= w, let A be the path (x, v1 , v2 , . . . , vk , v = vk+1 , vk+2 , . . . , vm , w), that is, the portion of the cycle between x and w containing no vertices of H except x and w. Since H together with A is 2-connected, it is G, as desired. If x = w then x = w = u. Let y be a vertex of H other than u. Since G is 2-connected, there is a path P from v to y that does not include u. Let vj be the last vertex on P that is in {v1 , . . . , v, . . . , vm }; without loss of generality, suppose j ≥ k+1. Let z be the first vertex on P after vj that is in H. Then let A be the path (u, v1 , . . . , v = vk+1 , . . . , vj , . . . , z), where from vj to z we follow path P . Now H ∪ A is a 2-connected subgraph of G, but it is not G, as it does not contain the edge {u, vm }, contradicting the maximality of H. Thus x ̸= w. DEFINITION 1.4.11 If G is a graph, β(G) = |E(G)| − |V (G)| + 1 is the cyclomatic number or Betti number of G. When we prove the main lemma, 1.3.6, the induction will be on β(G). It is easy to see that if G = H ∪ A as in lemma 1.4.10, β(H) = β(G) − 1. If G is 2-connected and β(G) = 1, G is a cycle. When β(G) = 2, G is a θ-graph, and this will be the base case for the induction. Because θ0 is excluded in our result, the case β(G) = 3 will require that we can remove a handle from G to get a θ-graph that is not θ0 . This is always possible, and not hard to prove, but somewhat tedious. We need to see that after adding a handle to θ0 , we can remove a handle to leave a θ-graph that is not θ0 . LEMMA 1.4.12 than θ0 . If β(G) = 3, it is possible to remove a handle leaving a θ-graph other 16 Chapter 1 Graph puzzles Proof. There are eight distinct ways to add a handle to θ0 : • • •. v • • • • •. • • • • •. • • • • • • • • • • • • • • •. • • • • •. • • •. • • • • • • • • • • •. • • •. • • • • • • In the first case, we may remove the handle with interior node v to form a θ-graph of type (x, 0, 4). The rest are similar. Exercises 1.4. 1. Let Σ be the set of 3-cycles in G. Show that ⟨Σ⟩ is the set of all products of 3-cycles. 2. If τ : X → Y is a bijection, and a, b, c ∈ X, verify that τ (a, b, c)τ −1 = (τ (a), τ (b), τ (c)). 3. State and prove a theorem analogous to the previous exercise, with (a, b, c) replaced by any cycle (a1 , a2 , . . . , ai ). 4. Show that a doubly transitive group is primitive. 5. In the definition of doubly transitive (1.4.7), show that if |X| ̸= 2, then the requirement that G be transitive is not necessary. That is, if G is a permutation group such that for every x, y, z ∈ X, with x ∈ / {y, z}, there is a σ ∈ G such that σ(x) = x and σ(y) = z, then G is transitive. 6. Prove that if |X| ≥ 4 then A(X) is doubly transitive on X. 7. A permutation group G on X is 2-transitive if for all w ̸= x and y ̸= z there is σ ∈ G such that σ(w) = y and σ(x) = z. Show that G is 2-transitive if and only if G is doubly transitive. 8. Finish the proof of lemma 1.4.12. 1.5 Proof of the Main Lemma We are now prepared to prove the main lemma, 1.3.6. As we remarked on page 11, it suffices to show that A(V (G)\{v}) ⊆ Γ(v) for a single vertex v in G. The proof is by induction on β(G), with base case β(G) = 2, that is, when G is a θ-graph other than θ0 . 1.5 Proof of the Main Lemma 17 Let G be a simple θ-graph with vertices of degree three y and z. Denote the three paths between y and z by p1 , p2 , and p3 , with p1 = (z, an , an−1 , . . . , a1 , y) p2 = (y, bm , bm−1 . . . , b1 , z) q = (v, c1 , c2 , . . . , cs , y) r = (v, d1 , d2 , . . . , dt , z) p3 = qr, where v is an internal vertex of p3 . a2 a1 • • y• • cs • bm • • •. • c1 v d1 an • •z dt • b1 • b2 Now let π = σqp2 p1 q = (a1 , . . . , an , z, b1 , . . . , bm ) ρ = σrp1 p2 r = (b1 , . . . , bm , y, a1 , . . . , an ). These are in Γ(v). Assume first that n ≥ 1 and that {m, n} is not {1, 2}, {2, 2}, or {2, 4}, so G is not of type (4, 2, 2), (2, 2, 2), or (2, 2, 1). By lemma 1.4.9, A({a1 , . . . , an , b1 , . . . , bm , y, z}) ⊆ ⟨π, ρ⟩. This implies that every 3-cycle with support in {a1 , . . . , an , b1 , . . . , bm , y, z} is in Γ(v). Let τ = σqp2 r = (d1 , . . . , dt , z, b1 , . . . , bm , y, cs . . . c1 ) ∈ Γ(v). We can produce a 3-cycle in Γ(v) containing a1 and any vertex in {c1 , . . . , cs , d1 , . . . , dt } in the form τ p (a1 , y, z)τ −p . Thus, the 3-cycles in Γ(v) generate a subgroup transitive on V (G)\{v}, and so by lemma 1.4.5, A(V (G)\{v}) ⊆ Γ(v). Now suppose that G is of type (4, 2, 2). Let n = 4, m = 2, s = 1, and t = 0. Then 2 τ ρπ −1 τ −2 π −1 ρ = (z, a4 , a1 ). We can then produce a 3-cycle mapping z to any vertex in V (G)\{v} in the form ρp (z, a4 , a1 )ρ−p or τ 4 (z, a4 , a1 )τ −4 (z, a4 , a1 )2 = (z, c1 , a4 ). Once again the result follows from lemma 1.4.5. If G is of type (2, 2, 2), let m = n = 2, s = 1, and t = 0. Then ρτ −1 ρπ −1 τ π 2 ρπ 2 ρ−1 = (z, a1 , c1 ). We can then produce a 3-cycle mapping z to any vertex in V (G)\{v} in the form ρp (z, a1 , c1 )ρ−p 18 Chapter 1 Graph puzzles Now let G be a simple 2-connected graph with β(G) ≥ 3. Write G = H ∪ A as in lemma 1.4.10; by lemma 1.4.12, we may do this so that H is not θ0 when β(G) = 3. Let v and w be the endpoints of the handle A. Since ΓG (v) ⊇ ΓH (v), ΓG (v) contains a 3-cycle, and so by lemma 1.4.8 it suffices to show that ΓG (v) is doubly transitive on V (G)\{v}. Let A be the path p = (v, at , at−1 , . . . , a1 , w). Let u be a vertex of H other than v and w. Since H is 2-connected, there is a simple path q = (w, bs , . . . , b1 , v) in H that does not include u. Then let σ = σpq = (w, a1 , . . . , at , b1 , . . . , bs ), so σ i (w) = ai and σ(u) = u. By the induction hypothesis, A(V (H)\{v} ⊆ ΓH (v), so for all vertices x of H, other than u and v, ΓH (v) contains a permutation mapping w to x and fixing u (see exercise 6 in section 1.4). Thus, for all vertices u in H, other than v and w, and for all vertices y and z in G, other than v and u, there is a permutation in ΓG (v) mapping y to z and fixing u. Finally, we need to show that for all u in {w, a1 , . . . , at } and vertices y and z in V (G)\{v, u}, there is a permutation in ΓG (v) mapping y to z and fixing u. Let x ∈ V (H)\{v, w}; there is a permutation τ ∈ ΓG (v) such that τ (u) = x. Then as we have already seen, there is a permutation µ mapping τ (y) to τ (z) and fixing x. Thus τ −1 µτ maps y to z and fixes u. Exercises 1.5. 1. In the case that G is of type (2, 2, 2), Verify that ρτ −1 ρπ −1 τ π 2 ρπ 2 ρ−1 = (z, a1 , c1 ). 1.6 The 15-puzzle redux Let’s return to the 15-puzzle. In graph form, this is a bipartite graph, so we know that puz(G) has two components. We are interested in the component that contains the “standard” labeling shown in figure 1.2.1; call this labeling f . Suppose that g is a labeling with the same blank vertex. By theorem 1.3.7, g is in the same component as f if and only if g −1 f has the same parity as 0, that is, that g −1 f is an even permutation of the vertices. It is a little more natural to think of permuting the labels, rather than the vertices. The corresponding permutation of the labels is f g −1 , which has the same parity as g −1 f . Thus it is easy to determine which configurations can be reached in the puzzle. Exercises 1.6. 1. Show that f g −1 has the same parity as g −1 f . 2. Which of the following configurations (a,b,c) can be produced from the standard starting position (shown for reference)? 1.6 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 . 14 15 • • • The 15-puzzle redux • 1 • 5 • 9 • 13 • 1 • 2 • 3 • 4 • 1 • 2 • 3 • 4 • 2 • 6 • 10 • 14 • 12 • 13 • 14 • 5 • 8 • 7 • 6 • 5 • 3 • 7 • 11 • 15 • 11 • • 15 • 6 • 9 • 10 • 11 • 12 • 4 •. 8 • 12 • • 10 •. • 8 • 7 • •. 15 • 14 • 13 • (a) 9 (b) (c) 19 Bibliography [1] A. F. Archer, A modern treatment of the 15 puzzle, Amer. Math. Monthly, 106 (1999), pp. 793–799. [2] R. M. Wilson, Graph puzzles, homotopy, and the alternating group, Journal of Combinatorial Theory (B), 16 (1974), pp. 86–96. 21 Index A S adjacent labelings, 8 support, 12 B T Betti number, 15 theta graph, 10 transitive, 12 2-transitive, 16 doubly, 13 2-transitive, 16 C cyclomatic number, 15 D doubly transitive, 13 H handle, 15 L labeling, 8 adjacent, 8 P primitive, 13 puz(G), 8 R reverse (of a path), 9 23