2. Prove that for any nontrivial connected graph G there exists a subset X of V(G) with |X|= K(G) such that every vertex in X is adjacent to at least one vertex in V(G) - X. [6 marks]

Fig: 1