Show that a graph is bipartite if and only if it does not have a cycle of odd length

In this article, we will prove that a graph is bipartite if and only if it does not have a cycle of odd length.

First, we will prove that if a graph is bipartite then it doesn’t have a cycle of odd length.

Proof

We will prove this by contradiction.

Suppose a Bipartite Graph G(V, E). Let V1 and V2 be the bipartitions of G. Assume graph G contains an odd cycle of length N.

Since the graph is bipartite. We must be able to divide the vertices of the odd length cycle in sets V1, V2 such that no adjacent vertices belong to the same set.

This shows that if a graph contains an odd length cycle, it cannot be bipartite since we cannot partition the vertices of the odd cycle in sets V1 and V2 such that no adjacent vertex belongs to the same set.

Therefore, our assumption that the bipartite graph G contains an odd cycle is incorrect. Hence, we can say that a bipartite graph does not have a cycle of odd length.

Next, we will prove that if a graph doesn’t contain an odd cycle or if a graph contains only even cycles, then it must be bipartite.

Proof

Suppose a connected graph G that contains only even cycles. Let v ∈ V(G).

X = { x | vertex x is at even distance from v }

Y= { y | vertex y is at an odd distance from v }

X ∪ Y = V(G), which is true since a vertex must be at an even distance or odd distance from v.

X ∩ Y = ∅, this statement is also true. This is because if a vertex is at both even distance and odd distance from v then the graph must contain an odd cycle. But it is not possible since graph G only contains only even cycles.

Next, we need to prove that no vertices in the same set are adjacent to each other.

Let x, y ∈ X. Both x, y are at an even distance from v.

• Distance from v to z is W.
• Distance from z to x is P.
• Distance from z to y is Q.

Since,

1. W + P = EVEN_NUMBER
2. W + Q = EVEN_NUMBER

This implies that the parity of P and Q is always the same. That means P and Q are either both even or odd.

If there exists an edge between x and y. Then it will form an odd cycle, z-x-y-z. But this is not possible since G contains only even cycles. Therefore, we can conclude that no pair of vertices in X are adjacent to each other.

Similarly, we can prove that no pair of vertices in set Y are adjacent to each other.

We have divided the vertices in sets X and Y such that no vertices belonging to the same set are adjacent to each other. Therefore, graph G is bipartite. We can say that if a graph contains only even cycles then it is bipartite.

We proved 2 statements

• If a graph is bipartite, then it doesn’t contain an odd cycle.
• If a graph doesn’t contain an odd cycle, then it is bipartite.

Using the above proofs, we can conclude that a graph is bipartite if and only if it does not have a cycle of odd length.

Read
Prove Hypercube is Bipartite
Prove Petersen Graph is Non-planer

References
Graph is Bipartite iff No Odd Cycles