5-connected Graphs And The Hamilton Question

Seymour's conjecture that every 5-connected non-planar graph contains a K₅subdivision, and the Hamilton question are two important questions in graph theory. Inthis thesis, through considering the 5-connected graph with the minimum edge numberand the Hal graph (self-definition), we obtain an important result about Seymour'sconjecture and two su?cient conditions about the Hamilton cycle and the Hamiltonpath, that further improve the results of Bondy and Chva′tal. We pay particularattention to the Hamilton question. The results obtained in this thesis are the two onfollows.1 By studying the propositions of a 4-separation set of the graph, which is obtainedby deleting an arbitrary edge of a 5-connected graph with the minimum edge number,we get an important result, that is every 5-connected graph containing a K₅-{e1,e2}subdivision such that e1 and e2 are two non-adjacent edges of K₅.2 We first give a definition of the Hal graph and find some propositions of it, thenprove a important theorem, namely, for every graph with v(G)≥6, if it satisfies someconditions, it must have one spanning sub-graph that is isomorphic to some Hal graph.Using the theorem, we further obtain two su?cient conditions about the existence ofthe Hamilton cycle and the Hamilton path, and give the best possible number with it.Furthermore, before giving the principal results, we introduce the application ofgraph theory, and the history and the present condition, some backgrounds of theproblems considering in the thesis, and the main work. In the end, we present somerelated notions and concepts.