Hamilton Circles In Infinite Planar Graphs

As a landmark in the verification of the Four Color Theorem,Hamilton cycles attract wide interests.It is also well known that the problem of deciding whether a given graph exists a Hamilton cycle or not is NP-complete,which brings forth a new challenge and makes mathematicians fascinate on this research work.The work on Hamiltonian cycles of 4-connected planar graphs dates back to the 1930s,when Whitney proved that every finite 4-connected planar triangulation contains a Hamilton cycle.This result was generalized by Tutte to all finite 4-connected planar graphs in 1956.Subsequent study by Thomassen in 1983 showed that every finite 4-connected planar graph is in fact Hamiltonian connected.To generalize Tutte's result even further to infinite graphs,Bruhn conjectured that every infinite locally finite 4-connected planar graph admits a Hamilton circle.In 2005,Yu showed it for every infinite locally finite 4-connected planar graph with exactly one end.Recently,Bruhn and Yu proved this conjecture also holds for locally finite 6-connected planar graphs with finitely many ends.The main contribution of this thesis is the establishment of a major case of Bruhn's conjecture,namely:Every infinite locally finite 4-connected planar graph with no dividing cycle admits a Hamilton circle.This thesis is organized as follows.We begin in Chapter 1 with a brief description of the development of Hamilton cycles in finite graphs,a summary of the known facts of Hamilton cycles in infinite planar graphs,formal definitions of some terms and notations to be necessary for stating and proving results,and make a precise statement of the main theorem.We then present a topological structure of infinite graphs,defined by Diestel and K(u|¨)hn,which makes the research on Hamilton circles of infinite planar graphs become feasible.In addition, we introduce the main tool in our proof-Tutte subgraph technique.We mention two known results,each of which proved the existence of certain Tutte paths in finite 2-connected planar graphs.They provide flexible techniques for extending Tutte subgraphs in the later proofs.To escape from the trouble of maintaining 4-connectivity,we take a novel approach by defining a new connec- tivity(called(4,C)-connected) for those 2-connected planar graphs which are almost 4-connected.We also indicate a certain plane representation of planar graphs,called nice embedding to explain the structure of infinite planar graphs clearly.Moreover,we describe the structure of infinite planar graphs with no dividing cycles.The proof of the main result will primarily rely on these conditions and structures.Finally,we state a detailed overview of the proof for the main result,which will assist readers to have a clear clue of the proof.Chapter 2 is devoted to two essential results of Tutte subgraphs in the layered structure of 4-tuples.First,we define 4-tuples to easily describe a special structure of infinite locally finite planar graphs and give the results of even layers and odd layers,respectively,to show that for a 4-tuple(G,H,x,y)(G is(4,C)-connected), there exist 4-tuples associated with subgraphs or almost subgraphs B₁,B₂,...,B_k of G such that a certain Tutte subgraph T′of∪_i=1^k B_i can be extended to a Tutte subgraph T of G,where the closure of T forms a circle or an arc.They are benefit for the illumination of the layered structure of Tutte subgraphs in 4-tuples.In Chapter 3,we give the proof of our desired main result.We start with the concept of the convergency of a sequence of finite paths,a variation of the K(o|¨)nig Infinity Lemma,and a Bruhn and Stein's result about the sufficient and necessary conditions of forming a circle in a locally finite graph.Based on these known facts and related to the definition of forward paths,we show a structural result for 4-tuple(G,H,x,y)(G is(4,H)-connected):There exists an H-Tutte subgraph T of G containing an edge of H such that the closure of T in |G| is an arc between x and y.Finally,we conclude that if an infinite locally finite 2-connected planar graph G with no dividing cycle has at least two ends,then G contains a Tutte subgraph T whose closure in |G| is a circle.In combination of Yu's result on locally finite planar graphs with exactly one end,we complete the proof of the desired result.