Constructions of cubic bipartite 3connected graphs with no Hamiltonian cyclesAlexander KelmansRUTCOR, Rutgers Univesity and University of Puerto Rico, San Juan
September 17,

ABSTRACT


Tutte conjectured that any cubic, bipartite, and 3connected graph is Hamiltonian. It is also natural to consider Tutte's conjecture for cubic, bipartite, and cyclically 4connected graphs. We discribe different constructions of cubic, bipartite, and 3connected graphs having no Hamiltonian cycle. Some of these constructions provide (infinitely many) graphs that are not only 3connected but, moreover, cyclically 4connected. The minimal such graph has 50 vertices and this graph is a minimal known counterexample to Tutte's conjecture. Moreover by means of these constructions we prove that if Barnette's conjecture (any cubic, bipartite, 3connected and planar graph is Hamiltonian) is true, then a much stronger result is also true. No preparation is needed to understand this talk. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

