Let G be a bipartite graph with partite sets U and W where (G) = r 1 and (G) < r.

(a) Use Theorem 8.15 to show that if there is an r-regular bipartite graph H containing G as a

subgraph such that at least one of the partite sets of H is U or W, then (G) = (G)

(thereby giving an alternative proof of Knig's Theorem 10.17 for such graphs G).

(b) Show that there need not be an r-regular bipartite graph H containing G as a subgraph such

that at least one of the partite sets of H is U or W.