 Solution

We construct an injection from the unmatched vertices in a matching to the leaves of a rooted tree. Start a downward graph path at each unmatched vertex $u$. If the current vertex is a leaf of a rooted tree, stop. Otherwise choose any child $v$. The current vertex is either the unmatched starting point or a vertex already matched to its own parent.

In either case, $v$ cannot be unmatched: the proper matching in a rooted tree condition would require its parent to be matched to one of $v$'s siblings in a rooted tree, whereas that parent is either unmatched or already matched upward. Nor can $v$ be matched to its parent. Its matching partner must therefore be one of its own children, say $w$. Extend the graph path by the two edges to $v$ and then to $w$, and continue from $w$.

Every extension descends two levels, so finiteness guarantees termination at a leaf of a rooted tree. Every visited vertex except the starting point is matched. The constructed graph paths for different unmatched starting points are disjoint: if two downward graph paths in a tree meet, one starting point must lie on the other path, which would put a second unmatched vertex after the first. That is impossible. Hence their terminal leaves of a rooted tree are distinct, provingOnly the properness condition for unmatched non-root vertices was used. If the root is unmatched and the convention exempts it because it has no parent, the same construction starts there and still works. Thus the root convention does not affect the claimed inequality. This proves the unmatched-vertex bound for a proper tree matching without requiring $M$ to have maximum size.