Rosen states Halls marriage theorem as follows The bipartite

Rosen states Hall\'s marriage theorem as follows: The bipartite graph G=(V,E) with bipartition (V_1 V_2) was a complete matehing from V_1 to V_2 if and only if |N(A) greaterthanorequalto |A| for all subsets A of V_1. If B = { a, b, c} what is the value of |B|? In the bipartite graph on the right, what is the value of {N W,n,y} |. Suppose that G be a bipartite graph with bipartition (V_1, V_2) Cond 2. M is a completed matching in G form V_1 to V_2. Consider the following four statements each of which may be true or false? Every vertex in V_1 is matched in M. Every vertex in V_2 is matched in M. If G is not a complete bipartite graph, then every vertex of G is matched in M. M is a maximum matching in G.

Solution

i. As no. of elements is 3 , therefore |B| = 3

ii. |N{w,x,y}| = 3 ( As no. of edges from w,x,y are 3)

iii. a,b are true as M is complete matching in G so it forms a complete graph.

c is false as if M is not complete graph so there may be vertices which are not matched.

d true M is complete matching which is maximum possible matching.