Let B be an undirected tree with |V| nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime O(|V|).
I understand that the solution is:
Find all leaves. For each leaf if the parent edge has not been seen by another leaf, mark the edge to its parent as matching edge. Now delete all found leaves, its parents and the associated edges of the parents. Start over from the beginning.
Like that described here: How to find maximum matching edges in undirected tree
But I did not understand how this can be proved by induction on the height of the tree. Can you help with this?