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