CSA E0 221: Discrete Structures November 19, 2014

Chalk & Talk Session

König’s Theorem

Useful Definitions
Bipartite Graph :

A bipartite graph, also called a bigraph, is a set of vertices decomposed into two disjoint
sets such that no two vertices within the same set are adjacent.

Matching Number :

A matching in a graph G is a set of edges without common vertices. A maximal matching

Vertex Cover :

A vertex cover of a graph G is a set S of vertices of G such that every edge of G has at least
one of member of S as an endpoint. The smallest possible vertex cover for a given graph
G is known as a minimum vertex cover, and its size is called the vertex cover number.

Theorem 1 (König’s Theorem) Interplay of Matching Number and Vertex Covering Num-
ber in Bipartite Graph

Statement : In any bipartite graph, the number of edges in a maximum matching equals
the number of vertices in a minimum vertex cover.

Proof 1 Let G = (V, E) be a bipartite graph, and let V be partitioned into left set L
and right set R. Suppose that M is a maximum matching for G.
By definition of ”matching”, no vertex can cover more than one edge of M . Therefore
if a vertex cover with |M | vertices can be constructed, it is minimum.
If M is a perfect matching, i.e every vertex of the graph is incident to exactly one edge
of the matching, then |L| = |R| = |M |. Since every edge of G is incident on exactly one
vertex of L and on exactly one vertex of R, either L or R is a vertex cover of size |M |.
So, we can say that, in a bipartite graph with perfect matching, the number of edges in a
maximal matching equals the number of vertices in a minimum vertex cover.
1
[Link] theorem (graph theory)

1-1
 Otherwise, we can use an alternating path argument to construct a minimum vertex
cover. Given M , an alternating path is a path whose edges alternate between M and E\M .
Partition the vertex set V of G into subsets Si as described below. Next we’ll prove that
the union of the odd-indexed subsets is a vertex cover with |M | vertices.
• Let S0 consist of all vertices on which the edges in the maximal matching M are not
incident.
• For integer j ≥ 0, let S2j+1 be the set of all vertices v such that
1. v is adjacent via some edge in E\M to a vertex in S2j and
2. v has not been included in any previously-defined set Sk , where k < 2j + 1.
If there is no such vertex, but there are vertices which have not been included in any
of the previously-defined set Sk , then we arbitrarily choose one of those vertices and
let S2j+1 consist of that single vertex.
• For integer j ≥ 1, let S2j be the set of all vertices u such that u is adjacent via some
edge in M to a vertex in S2j−1 . Note that for each v in S2j−1 there is a vertex u
to which it is matched, otherwise v would have been in S0 . Therefore M sets up a
one-to-one correspondence between the vertices of S2j−1 and the vertices of S2j .
Claim : All the sets Si where i ≥ 0 are disjoint.
For a vertex v, which by construction appears for the first time in S2j−1 ,
• Vertex v cannot be matched to a vertex in S2k with k < j since vertices in S2k are
either unmatched (when k = 0) or matched to a vertex in S2k−1 (when k ≥ 1).
• Vertex v cannot be matched to a vertex u in S2k−1 with k ≤ j as the vertices in S2k−1
with k < j are matched to vertices in S2k with 2k < 2j − 1 and therefore cannot be
matched to v.
• Also, suppose that v was matched to u in S2j−1 then we can form an alternating path
starting at v by selecting an edge of E\M joining v to a vertex in S2j−2 , an edge of M
joining that vertex to a vertex in S2j−3 and so on, joining a vertex in Si to a vertex
in Si−1 via an edge of E\M if i is odd and via an edge of M if i is even, until the
process cannot be continued, which happens either when one reaches S0 or when one
reaches a set S2h+1 containing a single vertex with no edge joining it to any vertex
in the next lower level, S2h . Form a similar path starting at u. Joining these two
paths by the edge vu of M which produces a longer alternating path P . The path P
is simple, since if the alternating paths starting from v and u had a common vertex w
at level i, there would be an odd cycle containing w, which is impossible in a bipartite
graph. Since v and u are connected, by construction both the paths can end only in
S0 or both end in S2h+1 . The latter is impossible as that would form a cycle, so as a
consequence, the endpoints of P can only be distinct vertices in S0 . Hence the first
and last edges of P are in E\M and therefore P contains one more edge of E\M
than that of M . So by removing the edges of P ∩ M from M and adding the edges of
P ∩ (E\M ) to M we obtain a matching with one more edge than M , contradicting
that M is maximum.

1-2
 We have shown that every vertex of V is in exactly one of the sets Si . It follows that
the edges of M always join vertices in adjacent levels S2j−1 and S2j . Similarly, we can show
that no edge of E\M joins a pair of vertices both of which lie in an even level. For suppose
an edge of E\M joins a vertex in S2j to a vertex in S2k with k ≤ j then, if v is a vertex
in S2k with k < j, then any vertex joined to v by an edge of E\M lies in a level Si with
i ≤ 2k + 1 < 2j, and therefore v cannot be joined by an edge of E\M to a vertex in S2j .
On the other hand, by the same alternating path argument used above, two vertices in S2j
cannot be joined to each other by an edge of E\M .
Consequently, every edge of M has exactly one vertex in an odd set, and every edge of
E\M has at least one vertex in an odd set. The union of all of the odd sets is therefore a
vertex cover of G containing |M | vertices.

Since, we have been able to construct a vertex cover with |M | vertices, thus we can say
that, in a bipartite graph the number of edges in a maximum matching equals the number
of vertices in a minimum vertex cover.

1-3