Is concept of Bipartite Graph relevant only for Connected Graph?

2.2k Views Asked by At

Is concept of Bipartite Graph relevant only for Connected Graph? For Example : 4 vertices and just 2 Edges i.e. one from node 1 to node 2, and the another from node 2 to node 3. So, is this Disconnected Graph also a Bipartite Graph? Or Bipartite graph deals with Connected Graphs only?

2

There are 2 best solutions below

2
On BEST ANSWER

A bipartite graph only requires that the vertex set can be partitioned into two disjoint sets, say $A$ and $B$, such that every edge in $E$ connects a vertex from one of the sets, to the other. You can have isolated points. If one denotes the bipartite graph by $(A,B,E)$, then formally you will have a different bipartition depending on if you place an isolated vertex in $A$ or in $B$.

1
On

No, the definition works perfectly well for a disconnected graph. A graph is bipartite if and only if each of the connected components is bipartite.