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

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

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

StackExchange Computer Science Q#97850, answer score: 3