Prove that, if G is a bipartite graph with an odd number of vertices, then G is non-Hamiltonian Continuing with my studies in Introduction to Graph Theory 5th Edition by Robin J Wilson, one of the exercises asked to prove that, if $G$ is a bipartite graph with an odd number of vertices, then $G$ is non-Hamiltonian. This is what I've come up with. Is it strong enough?

Let graph $G$ be a bipartite graph with an odd number of vertices and G be Hamiltonian, meaning that there is a directed cycle that includes every vertex of $G$ (Wilson 48). As such, there exists a cycle in G would of odd length. However, by Theorem 2.1, a graph $G$ is bipartite if and only if every cycle of $G$ has even length (Wilson 33). Proven by contradiction, if $G$ is a bipartite graph with an odd number of vertices, then $G$ is non-Hamiltonian.

As an example, the picture below has 13 vertices so it must be non-Hamiltonian.


Suppose $G = (V , E)$ is a bipartite graph
with $V = V_1 \cup V_2$, where $V_1 \cap V_2 = \emptyset$ and no edge
connects a vertex in $V_1$ and a vertex in $V_2$. Suppose that $G$
has a Hamilton circuit. Such a circuit must be of the form
$a_1, b_1, a_2, b_2,...,a_k, b_k, a_1$, where $a_i \in V_1$ and $b_i \in V_2$
for $i = 1, 2,...,k$. Because the Hamilton circuit visits each
vertex exactly once, except for $v_1$, where it begins and ends,
the number of vertices in the graph equals $2k$, an even number. Hence, a bipartite graph with an odd number of vertices
cannot have a Hamilton circuit.
