Prove that a bipartite graph with an odd number of vertices is not hamiltonian

First we will define some basic terminologies.

Bipartite Graph: A graph is bipartite if we can spit the vertices of the graph in two distinct sets V1 and V2 such that no edge connects vertices belonging to the same set.

Hamiltonian Graph: A graph is hamiltonian if it contains a hamiltonian circuit. Hamiltonian circuit is the circuit that visits each vertex of the graph exactly once without repetition.

Proof that a bipartite graph with an odd number of vertices is not Hamiltonian

We will prove the above statement by contradiction. Suppose a bipartite graph G with an odd number of vertices. Let G be hamiltonian. If G is hamiltonian then there exists a cycle in the graph that visits each vertex exactly once. The hamiltonian cycle will have an odd number of vertices. But this is not possible. A bipartite graph cannot contain an odd cycle. Therefore, our assumption that G is hamiltonian is wrong. Therefore, we can say that a bipartite graph with an odd number of vertices is not hamiltonian.

You can find proof that a bipartite graph doesn’t contain odd cycle here.

Leave a Comment

Your email address will not be published.