Exercises Videos Notes Multiple-choice questions Apps

Related books

Chromatic Graph Theory Modern Graph Theory Graph Coloring Problems Introduction to Graph Theory Suggest a Book
2

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.

Level:
Printable version LaTeX source
delete flag offensive retag edit

updated Sep 27 '12

diego gravatar image diego flag of Argentina
71 7
POST AN EXERCISE POST A VIDEO POST NOTES POST MULTIPLE-CHOICE QUESTION

Stats

Posted: Jun 27 '12

Seen: 188 times

Last updated: Sep 27 '12