Show that if either (a) G is not 2-connected, or , (b) G is bipartite with bipartition (X, Y) where IXI different to lYI, then" G is non hamiltonian.

Question

This is a question I found in the Graph Theory book by Bondy and Murty (4.2.1). I do not know Graph theory (I am a biologist) but I am starting to use some results in my line of work and I really need to understand at least some of it, so any help with this would be very welcome.

Answer 1

To show that not 2-connected $\implies G$ not Hamiltonian, you can equivalently show that $G$ Hamiltonian $\implies$ 2-connected. To do this, take a graph with a Hamiltonian cycle, and think about why removing any one edge still leaves a path between any two vertices.

For (b) $\implies$ $G$ not Hamiltonian, assume there were a Hamiltonian cycle $v_1,v_1,\dots,v_n,v_1$, where without loss of generality $v_1$ is in the $X$ part. The nature of bipartite graphs is the vertices in the path would alternate between $X$ and $Y$, so that $v_1,v_3,v_5\dots$ are in $X$ and $v_2,v_4,v_6\dots$ are in $Y$. In particular, this would imply $n$ was even (since $v_1$ and $v_n$ are next to each other, so $v_n$ must be in $Y$), which would mean that there are the same number of vertices in the lists $v_1,v_3,\dots$ and $v_2,v_4,\dots$, contradicting (b).