Hall$$s Marriage Theorem asserts that a bipartite graph G$=$V$,$U$,$E has a

matching that matchesall vertices of the set V if andonlyif for eachsubset

S $$V$,|$R$($S$)|>=|$S$|$whereR$($S$)$isthesetofallvertices adjacent to a vertex

in S$.$ Check this property for the following graph with $($i$)$ V $=\{1,2,3,4\}$

and $($ii$)$ V $=\{5,6,7\}.$

$1234$

$567$

b$.$ You have to devise an algorithm that returns yes if there is a matching in

a bipartite graph G $=$V$,$U$,$E that matches all vertices in V and returns

no otherwise. Would you base your algorithm on checking the condition

of Hall$$s Marriage Theorem?