graph algorithm, approximation algorithm

Question

After removing the leaves of the dfs tree of a random graph , suppose the number of edges left is |S|, can we prove that the matching for that graph will be |S|/2?

Answer 1

Here's a proof.

Theorem: Let T be any tree with i leaves. There is a (|T|-i)/2 matching in T.

Proof: by induction. If T is a tree with i leaves, let T' be the tree that results when removing all the leaves from T. T' has j <= i leaves. Similarly, let T'' be the tree that results when removing all the leaves from T'. T'' has k <= j leaves.

Apply the theorem by induction to T'', so there exists a matching of size (|T''|-k)/2 = (|T|-i-j-k)/2 in T''. The set of edges T-T' contains at least j edges that are not incident to any edge in T'' or to each other (pick one incident to each leaf in T'), so add those edges to make a matching in T of size (|T|-i+j-k)/2. Since j >= k, this is at least (|T|-i)/2 edges. QED.

I've glossed over the floor/ceiling issues with the /2, but I suspect the proof would still work if you included them.