Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

BessieTheCow's blog

By BessieTheCow, 4 weeks ago, In English,

Today I'm going to talk about Kőnig's theorem in graph theory, which states that in a bipartite graph, the size of a maximum matching is the same as the size of a minimum vertex cover. I had a hard time understanding this theorem since the resources I found required either logical leaps as in the case of the Wikipedia article and the book the article referenced or advanced concepts such as linear programming. Therefore, I'm going to try to explain it in a more intuitive way here both as a review for myself and to help others learn.

Review of relevant concepts

Bipartite graph: A graph where the vertices can be partitioned into two sets such that every edge connects a vertex of one set to a vertex in the other set.

Matching: A subset of the edges in a graph such that no two edges in the subset share an endpoint. A matching with the greatest possible size in a graph is called a maximum matching. A matching is said to match a vertex if the vertex is an endpoint of some edge in the matching.

Alternating path: An alternating path of a matching is a path in the graph where the edges alternate between being in the matching and not being in the matching.

Augmenting path: An alternating path where the two vertices on both ends are unmatched.

Vertex cover: A subset of the vertices in a graph which includes at least one endpoint of every edge. An vertex in a vertex cover is said to cover an edge if it is incident to the edge. A vertex cover with the minimum possible size is called a minimum vertex cover.

Proof of the theorem

The proof for this theorem which I will present will also provide an efficient method of finding a minimum vertex cover given a maximum matching. It is based on the Wikipedia article and page 74-75 of a book that the Wikipedia article referenced.

Lemma 1 (Berge's lemma): Maximum matchings have no augmenting paths. Proof: Suppose we have a matching which has augmenting path. For each of the edges in the path, if it is in the matching, we'll remove it from the matching, and if it isn't in the matching we'll add it to the matching. The result will be a valid matching with a size 1 greater than what we started with, therefore the original matching isn't maximum.

Lemma 2: The size of the minimum vertex cover must be greater than or equal to the size of the maximum matching. Proof: Since no two edges share an endpoint in a matching, each vertex in the vertex cover can cover at most one edge in the matching. Therefore a vertex cover must not have less edges than the size of the maximum matching. This means that if we can construct a vertex cover with size equal to the size of a maximum matching, it will be a minimum vertex cover.

Now I'll show how to construct a vertex cover with the same size as a maximum matching.

Some definitions: Let $$$V$$$ be the set of vertices and $$$E$$$ be the set of edges in a bipartite graph. Let our graph $$$G = (V, E)$$$ be partitioned into two sets of vertices $$$X$$$ and $$$Y$$$ such that every edge has an endpoint in $$$X$$$ and an endpoint in $$$Y$$$. Let $$$M$$$ be a maximum matching in $$$G$$$. Let $$$U$$$ be the set of unmatched vertices under $$$M$$$ in $$$X$$$. Let $$$Z$$$ be the set of vertices which can be reached from a vertex in $$$U$$$ via an alternating path under $$$M$$$ (including the vertices in $$$U$$$). All alternating paths that I talk about in this post will start from a vertex in $$$U$$$. Let $$$S = Z \cap X$$$ and $$$T = Z \cap Y$$$, the vertices in $$$Z$$$ which are in $$$X$$$ and the vertices in $$$Z$$$ which are in $$$Y$$$ respectively. Let $$$N(S)$$$ be the set of vertices adjacent to a vertex in $$$S$$$.

Lemma 3: The alternating path from a vertex in $$$U$$$ to a vertex in $$$S$$$ ends with an edge which is in $$$M$$$, and the alternating path from a vertex in $$$U$$$ to a vertex in $$$T$$$ ends with an edge not in $$$M$$$. Proof: The first edge in the alternating path must not be in $$$M$$$ since the vertex in $$$U$$$ is unmatched. Paths from a vertex in $$$X$$$ to another vertex in $$$X$$$ must have even length, and paths from a vertex in $$$X$$$ to a vertex in $$$Y$$$ must have odd length. Since the edges alternate between being in and not being in $$$M$$$, even length paths end in a edge part of $$$M$$$ and odd length edges end in an edge not part of $$$M$$$.

Lemma 4: $$$N(S) = T$$$ Proof: Clearly, $$$N(S) \supseteq T$$$, since for every vertex $$$u \in T$$$, the previous vertex on an alternating path from a vertex in $$$U$$$ to $$$u$$$ is in $$$S$$$. Consider a vertex $$$u \in N(S)$$$. If $$$u$$$ is connected to a vertex $$$v \in S$$$ by an edge not in $$$M$$$, then the alternating path to $$$v$$$ can be extended to $$$u$$$ by that edge and therefore $$$u$$$ is in $$$T$$$. If $$$u$$$ is connected to a vertex $$$v \in S$$$ by an edge in $$$M$$$, then $$$u$$$ must be a vertex on an alternating path to $$$v$$$. This is because the alternating path to $$$v$$$ must end in an edge in $$$M$$$ due to lemma 3 above, and since $$$v$$$ is only incident to one such edge, $$$u$$$ must be the previous node in the alternating path to $$$v$$$. This means that $$$u$$$ is also in $$$T$$$ in this case. Now we know that $$$N(S) \subseteq T$$$, and since $$$N(S) \supseteq T$$$, $$$N(S) = T$$$.

Let $$$K = (X \setminus S) \cup T$$$. All edges must have at least one endpoint in $$$K$$$. To prove this, suppose there is an edge $$$e = (u, v)$$$ such that $$$u \in X$$$ and $$$v \in Y$$$, and $$$u, v \notin K$$$. Then $$$u \in S$$$ and $$$v \notin T$$$, which is a contradiction because of lemma 4 since $$$v \in N(S)$$$ but $$$v \notin T$$$. Therefore, $$$K$$$ is a vertex cover. Now I'll prove that $$$|K| = |M|$$$, by proving that all vertices in $$$K$$$ are matched by $$$M$$$ and no edge in $$$M$$$ matches two vertices $$$K$$$. All vertices in $$$K \cap X = X \setminus S$$$ are matched because the unmatched vertices in $$$X$$$ are all in $$$U$$$ and therefore $$$S$$$. All vertices in $$$K \cap Y = T$$$ are matched because otherwise, the alternating path to an unmatched vertex in $$$T$$$ would be an augmenting path contradicting lemma 1. If an edge $$$e \in M$$$ has both endpoints in $$$K$$$, one of the endpoints $$$u$$$ must be in $$$K \cap X = X \setminus S$$$ and the other endpoint $$$v$$$ must be in $$$K \cap Y = T$$$. By lemma 3 the alternating path to $$$v$$$ ends in an edge not in $$$M$$$, which means it can be extended to $$$u$$$ via $$$e$$$. This means $$$u \in S$$$ which is a contradiction. Since all vertices in $$$K$$$ are incident to an edge in $$$M$$$ and all edges in $$$M$$$ are incident to exactly one vertex in $$$K$$$, $$$|K| = |M|$$$ and $$$K$$$ is a minimum vertex cover by lemma 2.

Now we have a method to construct a minimum vertex cover in a bipartite graph given a maximum matching. $$$S$$$ and $$$T$$$ can be found by a simple DFS, so this entire construction takes linear time.

Practice problems

CSA Round #23: No Prime Sum, suggested by limabeans

COCI 19/20 Round 6: Skandi, suggested by -is-this-fft-

USACO 2011 November Gold Problem 3: Cow Steeplechase, suggested by -is-this-fft-

PacNW 2016 G: Maximum Islands, suggested by brandonzhang

BAPC 2017 E: Easter Eggs, suggested by brandonzhang

SWERC 2012 F: Sentry Robots, suggested by brandonzhang

Please comment below if you have any questions or if there's a part that I could have explained better. Thanks for reading!

 
 
 
 
  • Vote: I like it
  • +119
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi, thanks for sharing! Do you know of any good problems to practice the concept directly?

For starters, I recently solved No Prime Sum on CSA that almost directly applies this concept.

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Thanks for the post! I had heard about Konig's theorem but never bothered to actually read the proof before.

Also, I think that you meant: Let $$$S = Z \cap X$$$ and $$$T = Z \cap Y$$$, the vertices in $$$Z$$$ which are in $$$X$$$ and the vertices in $$$Z$$$ which are in $$$Y$$$ respectively.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it
»
3 weeks ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

There's also this problem (which I think is a bit harder then most of the others?): SER 2018 Abstract Art

The only online judge I'm aware of that supports SER 2018 solutions is icpcgate (see this page for the contest). You can create an account at https://icpcgate.org/login.php