# Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?

I came across this problem in Tim Roughgarden's course on Coursera:

In this problem you are given as input a graph $$T=(V,E)$$ that is a tree (that is, $$T$$ is undirected, connected, and acyclic). A perfect matching of $$T$$ is a subset $$F \subseteq E$$ of edges such that every vertex $$v \in V$$ is the endpoint of exactly one edge of $$F$$. Equivalently, $$F$$ matches each vertex of $$T$$ with exactly one other vertex of $$T$$. For example, a path graph has a perfect matching if and only if it has an even number of vertices.

Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it. (The two algorithms differ only in the choice of $$v$$ in line 5.)

Algorithm A:

While T has at least one vertex:
If T has no edges:
halt and output "T has no perfect matching."
Else:
Let v be a vertex of T with maximum degree.
Choose an arbitrary edge e incident to v.
Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."


Algorithm B:

While T has at least one vertex:
If T has no edges:
halt and output "T has no perfect matching."
Else:
Let v be a vertex of T with minimum non-zero degree.
Choose an arbitrary edge e incident to v.
Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."


Algorithm $$A$$ can fail, for example, on a three-hop path. Correctness of algorithm $$B$$ can be proved by induction on the number of vertices in $$T$$. Note that the tree property is used to argue that there must be a vertex with degree $$1$$; if there is a perfect matching, it must include the edge incident to this vertex.

However, I think I found a counter-example which shows that Algorithm B may not be correct. Am I missing something? Consider the following graph (say $$T$$):

Step 1: Let $$v=3$$ (all vertices have the same degree) and $$e=(2,3)$$. Remove $$e$$ along with vertices $$3$$ and $$2$$.

Step 2: Let $$v=1$$ and $$e=(0,1)$$. Remove $$e$$ along with vertices $$0$$ and $$1$$.

Step 3: No vertices are left. Hence we get the output: "T has a perfect matching."

But clearly, our original graph was not a perfect matching as all the nodes were of degree $$3$$.

Note: I assumed that ties are meant to be broken arbitrarily by the algorithm.

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Sep 27 '18 at 23:31

"Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching". Your graph is NOT a tree as it has a cycle $$0, 1, 2, 0$$.

Furthermore, your graph does have a perfect matching. In fact, the edges $$(2,3)$$ and $$(0,1)$$ obtained by your step 1, 2 and 3 is a perfect matching. And hence, it is not true that "our original graph was not a perfect matching as all the nodes were of degree 3". Plenty of graphs whose nodes are all of degree 3 have a perfect matching.

The algorithms are understated: When a vertex is deleted, all edges incident to that vertex are also deleted, otherwise we're left with dangling edges.

Consider the path tree $$A - B - C - D$$. Algo A chooses vertex $$B$$, and say, edge $$(B, C)$$. After deleting vertices $$B$$ and $$C$$, and all the edges, we're left with vertices $$A$$ and $$D$$ with no edges. Algo A halts, and incorrectly declares that $$T$$ doesn't have perfect matching (it does, $$\{ (A, B ), (C, D) \}$$).

Lets prove the correctness of algo B by induction. For $$\lvert V \rvert = 1$$, it correctly identifies that $$T$$ doesn't have perfect matching. For $$\lvert V \rvert = 2$$, it correctly identifies that $$T$$ has perfect matching. Clearly, for $$T$$ to have perfect matching, $$\lvert V \rvert$$ must be even. Assume algo B works for $$\lvert V \rvert = k$$. Let us add a new vertex $$v$$ and a new edge $$(v, w)$$ to $$T$$, where $$w$$ is some existing vertex in $$T$$. Clearly, for $$T$$ to have perfect matching, it must include edge $$(v, w)$$ (since that's the only way to match vertex $$v$$). By construction, algo B picks $$v$$ and removes edge $$(v, w)$$ in some iteration, leaving $$\lvert V \rvert = k - 1$$, which by inductive hypothesis, is correctly solved by algo B.

Therefore, algo B is correct.

The solutions to the other questions from the course are available on my blog.