35-4 Maximum matching

Recall that for an undirected graph $G$, a matching is a set of edges such that no two edges in the set are incident on the same vertex. In Section 26.3, we saw how to find a maximum matching in a bipartite graph. In this problem, we will look at matchings in undirected graphs in general (i.e., the graphs are not required to be bipartite).

a. A maximal matching is a matching that is not a proper subset of any other matching. Show that a maximal matching need not be a maximum matching by exhibiting an undirected graph $G$ and a maximal matching $M$ in $G$ that is not a maximum matching. ($\textit{Hint:}$ You can find such a graph with only four vertices.)

b. Consider an undirected graph $G = (V, E)$. Give an $O(E)$-time greedy algorithm to find a maximal matching in $G$.

In this problem, we shall concentrate on a polynomial-time approximation algorithm for maximum matching. Whereas the fastest known algorithm for maximum matching takes superlinear (but polynomial) time, the approximation algorithm here will run in linear time. You will show that the linear-time greedy algorithm for maximal matching in part (b) is a $2$-approximation algorithm for maximum matching.

c. Show that the size of a maximum matching in $G$ is a lower bound on the size of any vertex cover for $G$.

d. Consider a maximal matching $M$ in $G = (V, E)$. Let

$$T = \{v \in V: \text{ some edge in } M \text{ is incident on } v\}.$$

What can you say about the subgraph of $G$ induced by the vertices of $G$ that are not in $T$?

e. Conclude from part (d) that $2|M|$ is the size of a vertex cover for $G$.

f. Using parts (c) and (e), prove that the greedy algorithm in part (b) is a $2$-approximation algorithm for maximum matching.

(Omit!)