Exercise 8.3.1 : Define the graph Gn to have the 2n nodes

a0, a1, . . . , an?1, b0, b1, . . . , bn?1

and the following edges. Each node ai, for i = 0, 1, . . . , n ? 1, is connected to

the nodes bj and bk, where

j = 2i mod n and k = (2i + 1) mod n

For instance, the graph G4 has the following edges: (a0, b0), (a0, b1), (a1, b2),

(a1, b3), (a2, b0), (a2, b1), (a3, b2), and (a3, b3).

(a) Find a perfect matching for G4.

(b) Find a perfect matching for G5.