Exercise 5.

We say that a set of vertices \(A \subseteq V\) is a vertex cover if every edge of the graph is incident to a vertex in the cover (so a vertex cover covers the edges). Since \(V\) itself is a vertex cover, every graph has a vertex cover. The interesting question is about finding a minimal vertex cover, one that uses the fewest possible number of vertices.

1. Suppose you had a matching of a graph. How can you use that to get a minimal vertex cover? Will your method always work?

2. Suppose you had a minimal vertex cover for a graph. How can you use that to get a partial matching? Will your method always work?

3. What is the relationship between the size of the minimal vertex cover and the size of the maximal partial matching in a graph?