König定理的内容是，一个二分图中的最大匹配数等于这个图中的最小点覆盖数。看过Matrix67大牛的证明后感觉证的很累赘，于是自己写一个。与最大匹配相关的东西可以在这里看到。
假如已知最大匹配M，由最大匹配的定义可知，二分图K中的两个集合A,B中已经取出了最多个匹配点，即取出了最多个不共用一个点的路径。如果K中除了M中的点以外再没有其他任何点，那么显然K中所有路径已经被覆盖。如果K中除了M中的点还有其他点时，我们把这些点组成的集合定为L。对于任意x,y∈L，如果x∈A，y∈B，x,y间不可能存在路径，因为x,y∉M，x,y不能匹配。所以任意x∈L，如果x与其它点z连通，则z一定属于M。所以路径x--z也已经被z覆盖。由此可见，M中的点覆盖了所有存在的边，即最小点覆盖=最大匹配。
还有一个定理不知道是不是König定理的推论：最小路径覆盖=节点数-最大匹配数。最小路径覆盖是指，选择最少的不相交的简单路径，覆盖所有的点。这个定理只适用于有向无环图，无向无环图的话...今天折腾了很多大牛们也没有什么结果...寄希望于Matrix67大牛了。不过那种神牛级别的人物应该不会理会的吧？话说为了给他发个邮件还专门选了别的邮箱，没有用QQ的。啧啧啧...诶...