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