If G = (V, E) is an undirected graph, a spanning subgraph H of G in which each vertex has degree 1 is called a one-factor (or perfect matching) for G.
a) If G has a one-factor, prove that |V| is even.
b) Does the Petersen graph have a one-factor? (The Petersen graph was first introduced in Example 11.19.)
c) In Fig. 13.31 we find the graph K4 in part (a), while part (b) provides the three possible one-factors for K4. How many one-factors are there for the graph K6?
d) For n ∈ Z+, let an count the number of one-factors that exist for the graph K2n. Find and solve a recurrence relation for an.