2. (a) For a graph G = (V,E) a subset S ⊆ V is called a vertex cover, if every edge of G has at least one endpoint in S. Let M be a maximum matching in G and let

S = {v ∈ V : vu ∈ M for some u ∈ V}.

Show that S is a vertex cover of G.

(b) Assume that the graph G = (V,E) has maximum degree ∆. Show that G contains an independent set of size at least n/(∆+1).

(c) Let G = (V,E) be a graph with |V| = n ≥ 4. Suppose that α(G) ≤ √ n. Show that |E| ≥ n/4.

(d) Give an example of a bipartite graph on which the greedy algorithm uses 3 colours on a particular ordering of its vertices.