The Gallai-Edmonds theorem
Meeting Time:
Nov. 10, 2009, 2:00-2:50pm
Abstract:
The Gallai-Edmonds Theorem provides a structural characterization of all the maximum matchings in a graph. I will show a short proof using Hall's Theorem and deficiency.