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 .

The minimum cardinality of an edge cover in a graph G is called the edge 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.

Let G be a bipartite graph with bipartition , and let be a maximum matching of G.
Denote by U the set of - unsaturated vertices in , and by Z the set of all vertices connected by - alternating paths to vertices of U.

Set .

Then, we have that every vertex in T is -saturated and .

Define  .

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

For, otherwise, there would be an edge with one end in S and the other end in , contradicting that .

Thus is a covering of G and clearly

By Lemma 9.7, is a minimum covering, and the statement follows.