MA010 Tutorial 4—Solution to Problem 4
Fr´ed´eric Dupuis
Problem
A maximum independent set is a set of vertices such that no two of them are joined by an
edge. A covering of vertices by edges is a set of edges such that every vertex is an endpoint of
at least one of these edges. Prove that if G is a bipartite graph with every vertex having
degree at least 1, then the size of the largest independent set is equal to the size of the
smallest covering of vertices by edges.
Hint: Think of the relationship with K¨onig’s theorem (i.e. max matching = min vertex cover
in bipartite graphs). What is the complement of a vertex cover?
Solution
Denote the graph by G “ pV, Eq, let cpGq be the size of the minimum edge cover, and let
ipGq be the size of the maximum independent set. We prove the statement in two steps:
first, we show that ipGq ď cpGq, and then we show that there exists an edge cover of the
same size as the maximum independent set.
To show that ipGq ď cpGq, suppose that we have an edge cover Ec Ď E and an
independent set I Ď V with |I| ą |Ec|. Since Ec is an edge cover, every vertex v P I must
be adjacent to at least one edge in Ec, and since |I| ą |Ec|, there must be at least one edge
in Ec adjacent to two vertices in I. This contradicts the fact that I is an independent set.
Now, we show that there must exist an edge cover Ec with |Ec| “ ipGq. To do this, we
first observe that the complement of a vertex cover is an independent set, and vice-versa.
Now, K¨onig’s theorem tells us that in a bipartite graph, the size mpGq of a maximum
matching is equal to the size vpGq of a minimum vertex cover.
We now construct the edge cover Ec as follows. First, we find a maximum matching
Em in G, and derive from it a minimum vertex cover Vc Ď V , such that each edge in
Em is adjacent to exactly one vertex in Vc (and therefore to one vertex in the maximum
independent set V P Vc). We then add to Ec all the edges in the matching Em. This means
that Ec now automatically covers all vertices in Vc (as well as an equal number of vertices
from V zVc). Now, for each vertex v P V zVc that remains uncovered, we add one edge.
Since V zVc is an independent set, we need exactly one edge per uncovered vertex. Now
we are done: Ec is clearly an edge cover, and there is a one-to-one mapping between
edges in Ec and vertices in V zVc, and therefore |Ec| “ |V zVc|.
1