Problem $50.$ Show that the greedy algorithm will always produce a matching that is at least half as good, i$.$e$.$ if $\backslash ($ M$^\{*\}\backslash )$ is the maximum matching, then the greedy algorithm outputs a matching of size at least $\backslash (\backslash$left$|$M$^\{*\}\backslash$right$|/2\backslash ).$

Given a matching $\backslash ($ M $\backslash ),$ a vertex is said to be free if no edge in $\backslash ($ M $\backslash )$ is incident on it$,$ it is called matched otherwise $($ See Figure $6)$

Figure $6$: A bipartite graph and a matching in it