Question

a) What is a bipartite graph?

b) Which of the graphs Kn, Cn, and Wn are bipartite?

c) How can you determine whether an undirected graphis bipartite?

Short answer

1. It is a graph with a vertex set that can be partitioned into subsets \({V_1}\;\& \;{V_2}\)so that each edge connects a vertex in\({V_1}\;\& \;{V_2}\). The pair\(({V_1}\;,\;{V_2})\) is called a bipartition of V.
2. \({K_n}\;\)is only bipartite for \(n = 2\) and \({C_n}\;\)is bipartite for even n
3. A graph is bipartite if and only if there are no odd cycles

Step-by-step solution

Step 1: a bipartite graph

Bipartite graph

It is a graph with a vertex set that can be partitioned into subsets \({V_1}\;\& \;{V_2}\)so that each edge connects a vertex in\({V_1}\;\& \;{V_2}\). The pair\(({V_1}\;,\;{V_2})\) is called a bipartition of V.

Step 2: Part (b) solution

\({K_n}\;\)is only bipartite for\(n = 2\) since any other\(n = 2\) since any n will always contain a\({K_3}\;\).

\({C_n}\;\)is bipartite for even n

\({W_n}\;\)is never bipartite since we always have a\({K_3}\;\).

Step 3: Part (c) solution

A graph is bipartite if and only if there are no odd cycles. This provides proof for all the cases in part (b)