a) Give an example, with justification, of a graph G which is:
(i) bipartite and has a perfect matching,
(ii) bipartite and has no perfect matchings,
[5 marks]
Let G = (V, E) be a bipartite graph with parts V1 and V2 and suppose that G
has a perfect matching.
(b) Show that |V1| = |V2|.
[5 marks]
(c) Let G denote the complement of G. Show that the clique number ω(G)
satisfies
ω(G) ≥ |V1|.
[5 marks]
(d) Let W ⊆ V be any clique in G and let W1 := W ∩V1 and W2 := W ∩V2.
Stating clearly any results that you use, prove that
|W | = |W1| + |W2| ≤ |V2|.
[Hint: You might want to recall Hall’s Marriage Theorem.]
[5 marks]
(e) Prove that there exists a colouring of G with |V1| colours.
[5 marks]
(f) Deduce that
ω(G) = χ(G) = |V1|.
Sample Solution