1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So, the one example I mentioned in the question is a Bipartite Graph, as it have one isolated vertex. $\endgroup$ – Devendra Sharma Oct 13 '17 at 17:34
  • $\begingroup$ @RudrakshaBaplawat Yes. Let node $1$ and $3$ be in vertex set $A$, and node $2$ in $B$, then place node $4$ in whichever you wish. $\endgroup$ – Alex Clark Oct 13 '17 at 17:50
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ and since an isolated vertex is also a Bipartite graph, the example I mentioned above is Bipartite. $\endgroup$ – Devendra Sharma Oct 13 '17 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.