Kőnig's theorem (graph theory)

The bipartite graph shown in the above illustration has 14 vertices; a matching with six edges is shown in blue, and a vertex cover with six vertices is shown in red. There can be no smaller vertex cover, because any vertex cover has to include at least one endpoint of each matched edge (as well as of every other edge), so this is a minimum vertex cover. Similarly, there can be no larger matching, because any matched edge has to include at least one endpoint in the vertex cover, so this is a maximum matching. Kőnig's theorem states that the equality between the sizes of the matching and the cover (in this example, both numbers are six) applies more generally to any bipartite graph.

Minimum cut ${\displaystyle (S,T)}$ in the flow network ${\displaystyle G'_{\infty }}$

The following proof provides a way of constructing a minimum vertex cover from a maximum matching. Let ${\displaystyle G=(V,E)}$ be a bipartite graph and let ${\displaystyle A,B}$ be the two parts of the vertex set ${\displaystyle V}$. Suppose that ${\displaystyle M}$ is a maximum matching for ${\displaystyle G}$.

Construct the flow network ${\displaystyle G'_{\infty }}$ derived from ${\displaystyle G}$ in such way that there are edges of capacity ${\displaystyle 1}$ from the source ${\displaystyle s}$ to every vertex ${\displaystyle a\in A}$ and from every vertex ${\displaystyle b\in B}$ to the sink ${\displaystyle t}$, and of capacity ${\displaystyle +\infty }$ from ${\displaystyle a}$ to ${\displaystyle b}$ for any ${\displaystyle (a,b)\in E}$.

The size ${\displaystyle |M|}$ of the maximum matching in ${\displaystyle G}$ is the size of a maximum flow in ${\displaystyle G'_{\infty }}$, which, in turn, is the size of a minimum cut in the network ${\displaystyle G'_{\infty }}$, as follows from the max-flow min-cut theorem.

Let ${\displaystyle (S,T)}$ be a minimum cut. Let ${\displaystyle A=A_{S}\cup A_{T}}$ and ${\displaystyle B=B_{S}\cup B_{T}}$, such that ${\displaystyle A_{S},B_{S}\subset S}$ and ${\displaystyle A_{T},B_{T}\subset T}$. Then the minimum cut is composed only of edges going from ${\displaystyle s}$ to ${\displaystyle A_{T}}$ or from ${\displaystyle B_{S}}$ to ${\displaystyle t}$, as any edge from ${\displaystyle A_{S}}$ to ${\displaystyle B_{T}}$ would make the size of the cut infinite.

Therefore, the size of the minimum cut is equal to ${\displaystyle |A_{T}|+|B_{S}|}$. On the other hand, ${\displaystyle A_{T}\cup B_{S}}$ is a vertex cover, as any edge that is not incident to vertices from ${\displaystyle A_{T}}$ and ${\displaystyle B_{S}}$ must be incident to a pair of vertices from ${\displaystyle A_{S}}$ and ${\displaystyle B_{T}}$, which would contradict the fact that there are no edges between ${\displaystyle A_{S}}$ and ${\displaystyle B_{T}}$.

Thus, ${\displaystyle A_{T}\cup B_{S}}$ is a minimum vertex cover of ${\displaystyle G}$.[4]

No vertex in a vertex cover can cover more than one edge of ${\displaystyle M}$ (because the edge half-overlap would prevent ${\displaystyle M}$ from being a matching in the first place), so if a vertex cover with ${\displaystyle |M|}$ vertices can be constructed, it must be a minimum cover.[5]

To construct such a cover, let ${\displaystyle U}$ be the set of unmatched vertices in ${\displaystyle A}$ (possibly empty), and let ${\displaystyle Z}$ be the set of vertices that are either in ${\displaystyle U}$ or are connected to ${\displaystyle U}$ by alternating paths (paths that alternate between edges that are in the matching and edges that are not in the matching). Let

${\displaystyle K=(A\setminus Z)\cup (B\cap Z).}$

Every edge ${\displaystyle e}$ in ${\displaystyle E}$ either belongs to an alternating path (and has a right endpoint in ${\displaystyle K}$), or it has a left endpoint in ${\displaystyle K}$. For, if ${\displaystyle e}$ is matched but not in an alternating path, then its left endpoint cannot be in an alternating path (because two matched edges can not share a vertex) and thus belongs to ${\displaystyle A\setminus Z}$. Alternatively, if ${\displaystyle e}$ is unmatched but not in an alternating path, then its left endpoint cannot be in an alternating path, for such a path could be extended by adding ${\displaystyle e}$ to it. Thus, ${\displaystyle K}$ forms a vertex cover.[6]

Additionally, every vertex in ${\displaystyle K}$ is an endpoint of a matched edge. For, every vertex in ${\displaystyle A\setminus Z}$ is matched because ${\displaystyle Z}$ is a superset of ${\displaystyle U}$, the set of unmatched left vertices. And every vertex in ${\displaystyle B\cap Z}$ must also be matched, for if there existed an alternating path to an unmatched vertex then changing the matching by removing the matched edges from this path and adding the unmatched edges in their place would increase the size of the matching. However, no matched edge can have both of its endpoints in ${\displaystyle K}$. Thus, ${\displaystyle K}$ is a vertex cover of cardinality equal to ${\displaystyle M}$, and must be a minimum vertex cover.[6]

To explain this proof, we first have to extend the notion of a matching to that of a fractional matching - an assignment of a weight in [0,1] to each edge, such that the sum of weights near each vertex is at most 1 (an integral matching is a special case of a fractional matching in which the weights are in {0,1}). Similarly we define a fractional vertex-cover - an assignment of a non-negative weight to each vertex, such that the sum of weights in each edge is at least 1 (an integral vertex-cover is a special case of a fractional vertex-cover in which the weights are in {0,1}).

The maximum fractional matching size in a graph ${\displaystyle G=(V,E)}$ is the solution of the following linear program:

Maximize 1_E · x

Subject to: x ≥ 0_E

__________ A_G · x ≤ 1_V.

where x is a vector of size |E| in which each element represents the weight of an edge in the fractional matching. 1_E is a vector of |E| ones, so the first line indicates the size of the matching. 0_E is a vector of |E| zeros, so the second line indicates the constraint that the weights are non-negative. 1_V is a vector of |V| ones and A_G is the incidence matrix of G, so the third line indicates the constraint that the sum of weights near each vertex is at most 1. Similarly, the minimum fractional vertex-cover size in ${\displaystyle G=(V,E)}$ is the solution of the following LP:

Minimize 1_V · y

Subject to: y ≥ 0_V

__________ A_G^T · y ≥ 1_E.

where y is a vector of size |V| in which each element represents the weight of a vertex in the fractional cover. Here, the first line is the size of the cover, the second line represents the non-negativity of the weights, and the third line represents the requirement that the sum of weights near each edge must be at least 1. Now, the minimum fractional cover LP is exactly the dual linear program of the maximum fractional matching LP. Therefore, by the LP duality theorem, both programs have the same solution. This fact is true not only in bipartite graphs but in arbitrary graphs:

In any graph, the largest size of a fractional matching equals the smallest size of a fractional vertex cover.

What makes bipartite graphs special is that, in bipartite graphs, both these linear programs have optimal solutions in which all variable values are integers. This follows from the fact that in the fractional matching polytope of a bipartite graph, all extreme points have only integer coordinates, and the same is true for the fractional vertex-cover polytope. Therefore the above theorem implies:[7]

In any bipartite graph, the largest size of a matching equals the smallest size of a vertex cover.

In the graph shown in the introduction take ${\displaystyle L}$ to be the set of vertices in the bottom layer of the diagram and ${\displaystyle R}$ to be the set of vertices in the top layer of the diagram. From left to right label the vertices in the bottom layer with the numbers 1, …, 7 and label the vertices in the top layer with the numbers 8, …, 14. The set ${\displaystyle U}$ of unmatched vertices from ${\displaystyle L}$ is {1}. The alternating paths starting from ${\displaystyle U}$ are 1–10–3–13–7, 1–10–3–11–5–13–7, 1–11–5–13–7, 1–11–5–10–3–13–7, and all subpaths of these starting from 1. The set ${\displaystyle Z}$ is therefore {1,3,5,7,10,11,13}, resulting in ${\displaystyle L\setminus Z=\{2,4,6\}}$, ${\displaystyle R\cap Z=\{10,11,13\}}$ and the minimum vertex cover ${\displaystyle K=\{2,4,6,10,11,13\}}$.

Jenő Egerváry (1931) considered graphs in which each edge e has a non-negative integer weight w_e. The weight vector is denoted by w. The w-weight of a matching is the sum of weights of the edges participating in the matching. A w-vertex-cover is a multiset of vertices ("multiset" means that each vertex may appear several times), in which each edge e is adjacent to at least w_e vertices. Egerváry's theorem says:

In any edge-weighted bipartite graph, the maximum w-weight of a matching equals the smallest number of vertices in a w-vertex-cover.

The maximum w-weight of a fractional matching is given by the LP:[18]

Maximize w · x

Subject to: x ≥ 0_E

__________ A_G · x ≤ 1_V.

And the minimum number of vertices in a fractional w-vertex-cover is given by the dual LP:

Minimize 1_V · y

Subject to: y ≥ 0_V

__________ A_G^T · y ≥ w.

As in the proof of Konig's theorem, the LP duality theorem implies that the optimal values are equal (for any graph), and the fact that the graph is bipartite implies that these programs have optimal solutions in which all values are integers.

One can consider a graph in which each vertex v has a non-negative integer weight b_v. The weight vector is denoted by b. The b-weight of a vertex-cover is the sum of b_v for all v in the cover. A b-matching is an assignment of a non-negative integral weight to each edge, such that the sum of weights of edges adjacent to any vertex v is at most b_v. Egerváry's theorem can be extended, using a similar argument, to graphs that have both edge-weights w and vertex-weights b:[18]

In any edge-weighted vertex-weighted bipartite graph, the maximum w-weight of a b-matching equals the minimum b-weight of vertices in a w-vertex-cover.