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.

Fig: 1