A theorem of Tutte states that every 4-connected non-hamiltonian graph contains $K_{ 3,3}$ as a minor. We strengthen this result by proving that such a graph must contain $K_{ 3,4}$ as a minor, thereby confirming a special case of a conjecture posed by Chen, Yu, and Zang in a strong form. This result may be viewed as a step toward characterizing the minor-minimal 4-connected non-hamiltonian graphs. As a 3-connected analog, Ding and Marshall conjectured that every 3-connected non-hamiltonian graph has a minor of $K_{ 3,4}$, $\mathfrak{ Q}^+$, or the Herschel graph, where $\mathfrak{ Q}^+$ is obtained from the cube by adding a new vertex adjacent to three independent vertices. We confirm this conjecture.
Categories: math.CO