# 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.