2
$\begingroup$

Kőnig's Theorem is as follows:

If $G$ is a bipartite graph, then the maximum number of edges in a matching in $G$ is equal to the minimum number of vertices in a vertex cover in $G$.

The constructive proof of Kőnig's Theorem is as follows:

https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)#Constructive_proof

What I don't understand is:

  1. How the size of the matching could be increased by removing the matched edges from the alternating path and adding the unmatched edges in their place?
  2. Why can't any matching edge have two endpoints in the set $K$?
  3. Why $K$ is cardinality equal to $M$?
$\endgroup$

1 Answer 1

0
$\begingroup$

For 1: Recall that the set Z is formed by unmatched left vertices, and those that are reachable from there by an alternating path. That means that each such path has the form l1--r1==l2--r2==l3--r3-... where every pair l[i]--r[i] is an unmatched edge, and r[i]==l[i+1] is a matched edge (alternating, remember?)

Notice that since we're alternating, when we go left to right we always follow an unmatched edge, and right to left we always follow a matched edge.

If such a sequence ends in an unmatched right vertex r[k], then we can extend the matching by removing edges (r[i], l[i+1]) for 1≤i<k and adding (l[i], r[i]) for 1≤i≤k, increasing the sie of the matching by one.

Let me give a small example:

a
 \
  \
c==b
 \
  \
   d

Here, L={a, c} and R={b, d}, and M={(b,c)}. There is an alternating path a--b==c--d between unmatched vertices a and d. That means we can invert the status of the edges along the path, constructing a==b--c==d instead, to construct the larger matching M={(a,b), (c,d)}, proving that the matching wasn't maximum to begin with.

It should be easy to see the same logic applies to any path that ends on an unmatched right vertex.

Therefore, in a maximum matching, such an alternating path cannot exist. An alternating path starting from an unmatched vertex must always end at a matched vertex, or the matching wasn't maximum.

For 2: For every matched edge, either both its endpoints are in Z, or neither. (Proof: if the right endpoint is in Z, then it must be part of an alternating path that ended with an unmatched edge, and the path can be extended by continuing to the left endpoint, which would then also be in Z. Similarly, if the left endpoint is in Z, then it must be part of an alternating part that already includes the right endpoint, because alternating paths always follow matched edges when going right to left, and by definition there can only be one matched edge incident to any vertex.)

Now recall that K=(L \ Z) ∪ (R ∩ Z). If both endpoints are in Z, then only the right endpoint is in K. If both endpoints are not in Z, then only the left endpoint is in K. Either way, exactly 1 of the endpoints is in K.

For 3: This follows from 2 and the fact that every vertex in K is an endpoint of a matched edge (which is proven on Wikipedia).

$\endgroup$
1
  • $\begingroup$ Hi and welcome to Math.SE. It would be preferable to use MathJax for mathematical expressions. You can get started here, and a more complete reference can be found here. $\endgroup$ Commented May 2, 2021 at 14:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .