# 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.

• Yes, this is correct. – Brian M. Scott Dec 14 '16 at 21:41
• So the picture I just added in, as an example, has 13 vertices so that must be non-Hamiltonian as I just proved. – Learner Dec 14 '16 at 21:53