9.3. Matching and covering.
A vertex and an edge are said to cover each other in a graph G if they are incident in G. A vertex cover in G is a set of vertices which covers all edges of G. An edge cover in a graph G (without isolated vertices) is a set of edges that covers all vertices of G.
The minimum cardinality
of a vertex cover in a graph G is called the vertex covering number of G and denoted by .

If K is a vertex-covering of G and M is a matching of G, then K contains at least one end of each edges in M.
Thus, for any
matching M and any vertex-covering . If
is a maximum matching and
is a minimum covering then
In general, equality does not hold. However, if G is bipartite we do have the equality. To prove this equality, first we state a lemma.
Lemma 9.7.: Let M be a matching and K be a covering such that
.
Then M is a maximum matching and K is a minimum covering.
Proof.
If is a maximum
matching and
is a minimum
covering then
Since ,
so the statement follows.
Theorem 9.8. (König, 1931): In a bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum covering.
Proof.





Set .


Define .
Every edge of G must have at least one of its ends in .


Thus is a covering of G and clearly
By Lemma 9.7, is a minimum covering, and the statement
follows.