Thursday, January 23, 2014

The König-Egerváry Theorem

I wasn't there, so I'm just going to do a really short overview of the König-Egerváry theorem. It basically says that in a bipartite graph, the largest matching is the same size as the smallest vertex cover. It's kind of obvious that any cover has to be $\geq$ the size of a matching, but how do we prove equality? In the notes, he uses Hall's theorem to prove it. Hopefully this isn't too important.

Here are some notes from Georgia Tech, approaching the problem from a flow network perspective: The König-Egerváry Theorem