(a) Let G = (V, E) be the bipartite graph shown in Fig. 13.32, with V partitioned as X ˆª Y. Determine 8(G) and a maximal matching of X into Y.

b) For any bipartite graph G = (V, E), with V partitioned as X ˆª T, if f(G) denotes the independence number of G, show that |F| = β(G) - δ(G). (The independence number

of an undirected graph is defined in Exercise 25 for Section 11.5.)
c) Determine a largest maximal independent set of vertices for the graphs shown in Fig. 13.30(a) and Fig. 13.32.

Transcribed Image Text:

x1 yi y2 уз X5 Figure 13.32 Figure 13.31