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

Question

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."

Now, the answer key says:

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$):

If we follow B:

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.

Answer 1

"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.

Answer 2

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.