In this article, we will show that a bipartite graph has a unique bipartition if and only if it is connected.
Bipartite Graph: A Graph is bipartite if we can divide its vertices into two disjoint sets, V1 and V2 such that no edge connects vertices from the same set.
Unique Bipartition: Unique Bipartition means we can divide vertices into V1 and V2, in only one possible way. Moving a vertex from V1 to V2 or V2 to V1 will make the graph non-bipartite.
Proof
Suppose a Bipartite Graph G(V, E) of 2 connected components – K1 and K2. Let V1 and V2 be the bipartitions of G.
If G is bipartite, then its components K1 and K2 must also be Bipartite. Let X1, Y1 be the bipartitions of K1 and X2, Y2 be the bipartitions of K2.
K1 and K2 are disconnected. Thus, we can say that X1/Y1 and X2/Y2 are disjoint.
We can bipartition the graph G into set V1, V2 in 2 ways.
In simple words, if a graph is disconnected we can bipartition the vertices into set V1, V2 in more than one way. Thus, a disconnected bipartite graph cannot have a unique bipartition.
Therefore, we can say that a bipartite graph has a unique bipartition if and only if it is connected.