1. Consider a Halloween party. Consider the Graph G with vertices denoting people at the party

and an edge between 2 vertices if their costumes are related in some way. G contains 2k such

vertices and k such edges, where k is a positive integer.

(a) Prove that if G has no isolated vertices then it has exactly k connected components.

(b) Prove that if G has no isolated vertices then it has no vertices of degree >= 2.