Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

On the Hamiltonicity of Cubic, Polyhedral, Bipartite Graphs

Booth Id:

Robotics and Intelligent Machines


Finalist Names:
Clarke, Paul

Barnette's conjecture states that every cubic, planar, 3-connected, bipartite (Barnette) graph is Hamiltonian. The conjecture is a famous unsolved problem in the field of graph theory. Due to the difficulty of the problem, little progress has been made since the conjecture was posed forty years ago. In this project, a specific class of Barnette graphs are considered, which we call difficult graphs. Difficult graphs are Barnette graphs whereby every pair of adjacent quadrilateral faces in the graph satisfies a particular property. Pairs of faces satisfying this property will be called dangerous pairs. The main result of this project states that if all difficult graphs are Hamiltonian, then Barnette's conjecture is true. This result has the obvious implication that if one were to prove all difficult graphs are Hamiltonian, Barnette's conjecture would also be proven. This will be the subject of future research.

Awards Won:
American Mathematical Society: Third Award of $500