Subscribe to the weekly news from TrueShelf

0

Unmatchable edges of bipartite graphs

Prove that the following algorithm finds the unmatchable edges of a bipartite graph \(G\) (edges that aren't in any perfect matching): find a perfect matching in \(G\), orient the unmatched edges from one side of the bipartition to the other, and orient the matched edges in the opposite direction. Return the unmatched ones that have endpoints in different strongly connected components of the resulting digraph.

Now, given a bipartite and perfect matchable graph \(G\), show that there exists a vertex in \(G\) such that any edge incident to it is in some perfect matching.

Related Content