On Paths in Planar Graphs Daniel P. Sanders* DEPARTMENT OF MATHEMATICS THE OHIO STATE UNIVERSITY COLUMBUS, OHIO 43210-1174 e-mail: dsanders@math.ohio-state.edu ABSTRACT This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary, it is shown that every 4-connected planar graph has a Hamilton path between any two c 1997 John Wiley specified vertices x, y and containing any specified edge other than xy. & Sons, Inc. 1. INTRODUCTION In 1956, Tutte [5] showed that every 4-connected planar graph has a Hamilton circuit. He proved this by showing that every plane graph has a special kind of path. In this paper, it will be called a Tutte path, and is a generalization of a Hamilton path. It is convenient to consider only 2-connected graphs. In a 2-connected plane graph G, the exterior circuit is the circuit bounding the infinite face and will be denoted XG . For a subgraph H of G, the bridges of H in G are defined as follows. A trivial bridge of H in G is an edge in E(G) \ E(H) with both ends in V (H). A non-trivial bridge of H in G is a component K of G \ H with all vertices of H adjacent to vertices of K added and all edges with one end in H and the other in K added. The vertices of attachment of a bridge B of H in G are V (B) ∩ V (H). A bridge is attached to its vertices of attachment. A path (circuit) P, subgraph of a plane graph G, is a Tutte path (circuit) if and only if each bridge of P has at most three vertices of attachment and each bridge containing an edge of XG has at most two vertices of attachment. Lemma 1 (Tutte). Let G be a 2-connected plane graph. Let x, y, and α be two vertices and an edge, respectively, of XG . Then G has a Tutte path from x to y containing α. * The majority of this work was completed while the author was at the Georgia Institute of Technology. Journal of Graph Theory Vol. 24, No. 4, 341 345 (1997) 1997 John Wiley & Sons, Inc. c CCC 0364-9024/97/040341-05 342 JOURNAL OF GRAPH THEORY FIGURE 1. The edge cannot be removed from the exterior circuit. A Tutte path in a 4-connected graph is also a Hamilton path. Tutte's Theorem follows by choosing x and y to be adjacent. In 1983, Thomassen [4] improved this result by removing the restriction on the location of y. Lemma 2 (Thomassen). Let G be a 2-connected plane graph. Let x and α be a vertex and edge, respectively, of XG , and let y be any vertex of G distinct from x. Then G has a Tutte path from x to y containing α. Thomassen's Theorem that every 4-connected plane graph is Hamilton-connected easily follows from this lemma. Freeing the vertex y from being in XG allows the ends of the path to become arbitrary, giving the necessary Hamilton paths. For a proof of Lemma 2, see [4] and [1]. The main result of this paper generalizes Lemma 2, by removing the restriction on the location of x. Theorem. Let G be a 2-connected plane graph. Let α be an edge of XG , and let x and y be arbitrary distinct vertices of G. Then G has a Tutte path P from x to y containing α. Since x and α no longer have to share a face, this allows for more powerful results. For example, consider a 4-connected plane graph G. While Tutte's theorem shows that G contains a Hamilton circuit through any edge of G, the theorem presented here shows that G has a Hamilton circuit through any two edges of G. Further, let x and y be distinct vertices of G. Thomassen's theorem gives a Hamilton path in G from x to y. The theorem above guarantees a Hamilton path in G from x to y through any edge of G (except xy). These two results are stated below as Corollaries 1 and 2. Corollary 1. Let G be a 4-connected plane graph, x, y be vertices of G, and α 6= xy be an edge of G. Then G has a Hamilton path from x to y through α. Corollary 2. Every 4-connected plane graph has a Hamilton circuit through any two of its edges. The theorem above is as strong as possible in several ways. The edge α cannot be removed from XG , even if the vertices x and y are required to be on XG . In the graph of Figure 1, there is no Tutte path between the marked vertices containing the marked edge. Keeping α on XG , the direction that α is traversed cannot be specified, even if the vertices x and y are again both on XG . This is easily seen from planarity. In general, there is no theorem to find a path through two edges of XG , even if the vertices x and y are both required to be on the exterior circuit. Consider the circuit C4 with vertices a, b, c, d ON PATHS IN PLANAR GRAPHS 343 and edges ab, ad, bc, cd, embedded in the plane. There is no Tutte path in C4 from a to c through both ab and either ad or cd. Let D := C4 + bd, with bd embedded in the interior face of C4 . Then D has no Tutte path from a to c through both ab and bc. On the other hand, given a subset S of E(XG ), it may be possible to classify the structure of 2-connected plane graphs that do not have a Tutte path from x to y containing S. As a corollary, this would give necessary and sufficient conditions for a 2-connected plane graph without interior component 3-cuts (see [2]) to have a Hamilton circuit. 2. A PROOF OF THE THEOREM One more lemma is required. It is a useful tool for many planar problems, and will be referred to as the Three Edge Lemma. For a proof, see [2] or [3]. The Three Edge Lemma. three edges of XG . Every 2-connected plane graph G has a Tutte circuit through any If P is a path, and x and y are two vertices of P, then xP y will represent the subpath of P from x to y. If H and J are subgraphs of a graph G, then an H, J-connector in G is a bridge of H ∪ J in G with vertices of attachment in both H and J. Proof of the Theorem. The proof is by induction on the number of vertices of G. Clearly, the theorem is true for |V (G)| ≤ 4. Let 2-connected plane G be given. Let α be an arbitrary edge of XG , and let x and y be arbitrary vertices of G. From Lemma 2, the theorem follows trivially if x or y is a vertex of XG , so assume not. Also, if there is an edge ψ ∈ E(G) such that x or y is a vertex of XG−ψ , then the theorem follows trivially if Lemma 2 is applied correctly to G − ψ, so assume not. A Tutte path in a graph H with |V (H)| < |V (G)| from u through ω to v found by induction will be called a uωv-path in H. Assume first that there are subgraphs L and R of G such that L ∪ R = G, V (L) ∩ V (R) = {a, b} ⊂ V (XG ), x ∈ V (L), α ∈ E(L), y ∈ V (R), and R is 2-connected (or a similar structure with x and y swapped). Let c 6∈ V (G) be given. Let β := ab, L0 := L + c + ac + bc, with c embedded where R used to be, and R0 := R + β, with β embedded where L used to be. Since R is 2-connected, and y 6∈ V (XR0 ), |V (R)| ≥ 4, and thus |V (L0 )| < |V (G)|. Since x ∈ V (L), |V (R)| = |V (R0 )| < |V (G). Find an xαc-path PL in L0 by induction. Without loss of generality, assume b ∈ V (PL ). Case 1. a 6∈ V (PL ). Let γ be an edge of XR containing a and PR be a bγy-path in R by induction. Then set P := xPL b ∪ bPR y. Case 2. a ∈ V (PL ). Let PR be an aβy-path in R0 by induction. Then set P := xPL b ∪ bPR y. The path P is as desired in each case. If there are no such L and R as above, then x and y are in the same component of G \ XG . From elementary graph theory, there is a ‘‘path’’of blocks of G \ XG , the first having x as a vertex and the last having y as a vertex. Let B1 , B2 , . . . , Bk be the unique such ‘‘path’’of blocks of G \ XG with x ∈ V (B1 ), y ∈ V (Bk ), and k minimal. Let b0 := x, bi := Bi ∩ Bi+1 for Sk i := 1, . . . , k − 1, bk := y, and H := i=1 Bi . The (XG ∪ H)-bridges will now be grouped. Let s be a vertex of XG which shares a face with a vertex of H. For each (XG ∪ H)-bridge X, let QX be the minimal path in XG including all the vertices of attachment of X in XG such that s is not an interior vertex of QX . Further, let pX (qX ) be the most counterclockwise (clockwise) vertex of QK . Note that for two (XG ∪ H)-bridges 344 JOURNAL OF GRAPH THEORY X, Y, either QX ⊂ QY , QY ⊂ QX , or E(QX ) ∩ E(QY ) = ∅. Let an (XG ∪ H)-bridge X be maximal if there is no (XG ∪ H)-bridge Y distinct from X such that QX ⊂ QY , and QX 6= QY . Let the group of a maximal (XG ∪ H)-bridge X be the union of X and all (XG ∪ H)-bridges Y such that QY ⊂ QX , and QY 6= QX . Let the (XG ∪ H)-bridge groups be the groups of its maximal bridges. For each XG , H-connector group K, let vK be the unique vertex of attachment of K in H and iK (jK ) be the least (greatest) integer such that vK ∈ V (BiK ) (∈ V (BjK )). Let Kα be the XG , H-connector group such that α ∈ E(QKα ), or if there is none, an XG , H-connector group with pKα nearest to α counterclockwise from it. Since G is 2-connected, exchanging clockwise and counterclockwise in the definitions above if necessary, there is an XG , H-connector group K with pK 6= pKα . Let Lα be an XG , H-connector group with qLα nearest counterclockwise to QKα such that pLα 6= pKα . Let K1 , . . . , Km be all the XG , H-connector groups with pKi = pKα . Notice Kα = Ki for some i, and thus m ≥ 1. Let L1 , . . . , Ln be all the XG , H-connector groups with pLj 6= pKα , qLj = qLα . Notice pLα 6= pKα , and thus Lα = Lj for some j, and n ≥ 1. Let a1 and a2 be vertices not in G, and let γ := a1 a2 , δi := a1 vKi , and j := a2 vLj . Let f := min{min{jKi |1 ≤ i ≤ m}, min{jLj |1 ≤ j ≤ n}}. Let l := max{max{iKi |1 ≤ Sl i ≤ m}, max{iLj |1 ≤ j ≤ n}}. If qLα 6= pKα , let β := γ and J := ( i=f Bi ) + a1 + a2 + γ + δ1 + · · · + δm + 1 + · · · + n , with the extra vertices and edges embedded in a planar way in the infinite face. If qLα = pKα , note n = 1 and let a1 = a2 , β := 1 , and Sl J := ( i=f Bi ) + a1 + δ1 + · · · + δm + 1 , with the extra vertex and edges embedded in a planar way in the infinite face. Notice J is 2-connected, and since only at most two vertices were added while V (XG ), containing at least three vertices, was deleted, |V (J)| < |V (G)|. Thus induction gives PJ , a bf −1 βbl -path in J. For i < f or i > l, let ζi be an edge of XBi and Pi be a bi−1 ζi bi -path in Bi . There is exactly one integer i such that δi ∈ E(PJ ); let Kδ := Ki . There are two cases on how to define PKδ . Case 1. Kδ is a trivial XG , H-connector. Let PKδ := Kδ . Case 2. Kδ is a non-trivial XG , H-connector group. Let η := vKδ qKδ and M := Kδ ∪ QKδ + η, with η embedded in the infinite face such that V (QKδ ) ⊂ V (XM ). Let θ be an edge of XM containing pKδ . There are two cases on how to define a circuit C. Case 2a. α 6∈ E(QKδ ). Let C be a Tutte path in M from vKδ to qKδ through θ by Lemma 1. Case 2b. a ∈ E(QKδ ). Let C be a Tutte circuit through α, η, θ in M by the Three Edge Lemma. For each of Cases 2a and 2b, let PKδ := C − η. There is exactly one integer j such that j ∈ E(PJ ); let L := Lj . There are two cases on how to define PL . Case 1. L is a trivial XG , H-connector. Let PL := L . Case 2. L is a non-trivial XG , H-connector group. Case 2a. qLα 6= pKα . Let ι := vL pL , and Na := L ∪ QL + ι, with ι embedded in the infinite face such that V (QLα ) ⊂ V (XNα ). Let λ be an edge of XNα containing qL . Let D be the Tutte path in Na from vL to pL through λ by Lemma 1. Let PL := D − ι. ON PATHS IN PLANAR GRAPHS 345 Case 2b. qLα = pKα . Let κ := vL qL and Nb := L ∪ QL + κ, with κ embedded in the infinite face such that V (QL ) ⊂ V (XNb ). Let Pb be a pL κqL -path in Nb by induction. Let PL := vL Pb pL . Let P be the path in XG from pL counterclockwise to qKδ . Finally, let T := PJ ∪ Sk Sf −1 X ( i=1 Pi ) ∪ ( i=l+1 Pi ) ∪ PKδ ∪ PL ∪ PX − a1 − a2 . Now T can be modified to become a Tutte path P in G. For a bridge A of T with V (A) ∩ V (XG ) 6= ∅, let QA , pA , qA be defined as with XG , H-connectors. Also, let the bridges be grouped as before. If there is a non-trivial bridge group A of T with all its vertices of attachment in V (XG )∩V (T ), then let µ := pA qA and M := A ∪ QA + µ, with µ embedded in the infinite face such that V (QA ) ⊂ V (XM ). If α ∈ E(QA ), then let β := α, else let β be any edge of XM distinct from µ. Let C be a Tutte path in M from pA to qA through β by Lemma 1. Modify T by replacing QA by C in T. If there is a bridge group Aα of T remaining with α ∈ E(QAα ), then let ν := vAα pAα , ξ := vAα qAα , N := Aα ∪ QAα + ν + ξ, with ξ embedded in the infinite face such that V (QAα ) ⊂ V (XN ). (Notice that Aα = Kα .) Let C be the Tutte circuit through α, ν, ξ in N from the Three Edge Lemma. Modify T by replacing QAα by C − vAα in T. Note that every bridge group of T has at most two vertices of attachment not in V (XG ). In each case, a portion of T which is a subgraph of XG will be replaced by a path through the corresponding bridge group. Let R2 be a bridge group of T with two vertices of attachment not in V (XG ). Let u1 (u2 ) be the most counterclockwise (clockwise) vertices of attachment of R2 in XG . Let U be the path in XG from u1 clockwise to u2 . Notice U is a subgraph of T. Let v1 and v2 be the vertices of attachment of R2 not in XG such that ui and vi are in the boundary of some face Fi of G. Let πi := ui vi , ρ := v1 v2 , and H2 := R2 ∪ U + π1 + π2 + ρ, with π1 , π2 , ρ embedded in the infinite face such that V (U ) ⊂ V (XH2 ). Note H2 is 2-connected and plane; thus there is a Tutte circuit C2 through π1 , π2 , ρ by the Three Edge Lemma. Let P2 be the path from u1 to u2 in C2 not through v1 . Now T is modified by replacing U with P2 . Repeat this process for all such R2 . Let R1 be a bridge group of T with one vertex of attachment not in V (XG ). Let u1 (u2 ) be the most counterclockwise (clockwise) vertices of attachment of R1 in XG . Let U be the path in XG from u1 clockwise to u2 . Notice U is a subgraph of T. Let t be the vertex of attachment of R1 not in XG . Let σi := ui t and H1 := R1 ∪ U + σ1 + σ2 , with σ1 , σ2 embedded in the infinite face such that V (U ) ⊂ V (XH1 ). Note H1 is 2-connected and plane; thus there is a Tutte path P1 from u1 to t through σ2 by Lemma 1. Now T is modified by replacing U with u1 P1 u2 . Repeat this process for all such R1 . References [1] N. Chiba and T. Nishizeki, A theorem on planar graphs, J. Graph Theory 10 (1986), 449–450. [2] D. P. Sanders, On Hamiltonian cycles in certain planar graphs, J. Graph Theory 21 (1996), 43–50. [3] R. Thomas and X. Yu, 4-Connected projective planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994), 114–132. [4] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983), 169–176. [5] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99–116. Received November 9, 1993

1/--страниц