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