图算法，近似算法

Question

去除随机图的dfs树的叶子后，假设剩余的边数为| S |，那么我们能否证明该图的匹配为| S |/2？

Answer 1

这是一个证明。

定理：假设T是任何带有叶子的叶子i。在T有(|T|-i)/2匹配。

证明：通过归纳。如果T是一棵具有i叶子的树，则让T'成为从T中删除所有叶子时产生的树。 T'有j <= i叶。同样，假设T''是从T'中删除所有叶子时的结果树。 T''有k <= j叶。

通过归纳将定理应用于T''，所以在T''中存在大小为(|T''|-k)/2 = (|T|-i-j-k)/2的匹配。边缘组T-T'包含至少j边缘，其不会入射到T''中的任何边缘或彼此（在T'中挑选一个入射到每个叶子的边缘），所以添加这些边缘以在中进行匹配，其大小为(|T|-i+j-k)/2。由于j >= k，这至少是(|T|-i)/2的边缘。 QED。

我已经掩盖了/ 2的地板/天花板问题，但我怀疑证明如果包含它们仍然可以工作。