The Tutte Subgraph Method And Its Application

The Hamilton Cycle Problem is one of the most important problems in Mathematics and Computer Science.It is also related to the famous Four Color Theorein. In 1931,Whitney proved that every 4-connected planar triangulation has a Hamilton cycle(and hence,is 4-face-colorable).In 1956,Tutte generalized Whitney's result by showing that every 4-connected planar graph contains a Hamilton cycle.This was further extended by Thomassen in 1983.These proofs were by induction and relied on the existence of certain paths and cycles(later called Tutte subgraphs).The Tutte subgraph technique has now been used extensively to prove the existence of long paths and cycles in graphs embeddable on surfaces.Thomassen proved that every 4-connected planar graph is Hamiltonian-connected(conjectured by Plummer),Thomas and Yu showed that 4-connected projective-planar graphs are Hamiltonian(conjectured by Gr(u|¨)nbaum),Yu proved that 5-connected "locally planar" triangulations of any surface are Hamiltonian(conjectured by Thomassen),etc.In this thesis,we present two results by applying the Tutte subgraph technique. The first one deals with an old conjecture of Malkevitch(Chapter 2),while the second one concerns the maximum bipartite subgraphs in 3-connected cubic triangle-free planar graphs(Chapter 3).In Chapter 1,we introduce some basic graph theoretic definitions and notation which are used throughout the thesis.We also provide a brief survey of the literature dealing with Tutte subgraphs.In Chapter 2,we consider a conjecture of Malkevitch that every n-vertex 4-connected planar graph contains a cycle of length k for every k E {n,n-1,…,3} if it admits a cycle of length 4.Previous results showed that every n-vertex 4-connected planar graph has a cycle of length k for every k∈{n,n-1,…,n-6} with k＞3.By combining Tutte subgraphs and contractible subgraphs,we prove that for any n-vertex 4-connected planar graph G(with n≥9) and any vertex v of G,there always exists a cycle C of length n-6 in G such that v(?)V(C). We then use this result(as well as a result of Fontet and Martinov) to show that every 4-connected planar graph with n vertices contains a cycle of length n-7 provided n≥10.In Chapter 3,we study the maximum bipartite subgraphs in 3-connected cubic triangle-free planar graphs.Thomassen recently proved that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least 29|V(G)|/24-7/6 edges,improving previously known lower bound 6|V(G)|/5 (for cubic triangle-free graphs).It is easy to see that if G is a plane graph and S(?)E(G) such that G-S is bipartite,then we obtain an even graph from the dual graph of G by deleting its edges corresponding to edges in S.With this observation and by using the Tutte subgraph technique,Thomassen proved the following equivalent result:If G is a planar triangulation with minimum degree at least 4,then G has a set of at most 7|V(G)|/12 edges whose deletion results in an even graph.We extend Thomassen's technique by proving stronger results on Tutte cycles and improve this upper bound to 9|V(G)|/16-9/16.This implies that every 3-connected cubic triangle-free planar graph G contains a bipartite subgraph with at least 39|V(G)|/32-9/16 edges.