Introduction
A Hamiltonian graph is a graph that contains a Hamiltonian cycle. A Hamiltonian cycle, also known as a Hamiltonian path or Traceable path, is a cycle in a graph that visits every vertex exactly once, except for the starting vertex, which is visited again at the end to complete the cycle.
A Bipartite Graph is a graph whose vertices can be divided into two disjoint sets such that every edge in the graph connects a vertex from one set to a vertex in the other set. And there shouldn’t be any edges between vertices in the same set. Read more here.
Proof by contradiction
Assume that G is a Bipartite graph with an odd number of vertices, and also that G is Hamiltonian.
This means that there exists a Hamiltonian cycle in G, which is a cycle that visits every vertex exactly once. Since G is bipartite, the vertices of G can be partitioned into two sets, let’s call them A and B, such that every edge in G connects a vertex in Set A to a vertex in Set B.
Since G has an odd number of vertices, without loss of generality, let’s assume that Set A has n vertices and Set B has n-1 vertices.
Case I
Let Hamiltonian path starts from Set A.
Now, in order for the Hamiltonian cycle to exist, it must start and end at a vertex in Set A. However, since |A| = (n) and |B| = (n-1), the path will end at the last member of Set A. And in order to complete the Hamiltonian cycle, the last vertex of Set A should have an edge to the first vertex of Set A. This is a contradiction because in a Bipartite Graph, there couldn’t be any edges between vertices in the same set. Therefore, we can conclude that Graph G is Non-Hamiltonian.
Case II
Let Hamiltonian path starts from Set B.
Since |A| = (n) and, |B| = (n-1), there will always be one vertex in Set A that is not visited in the Hamiltonian cycle. This is a contradiction because the Hamiltonian cycle should visit every vertex exactly once, and if there is an unvisited vertex in Set B, the cycle is incomplete.
Therefore, we can conclude that Graph G is Non-Hamiltonian.