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.