嘿，我来帮你捋清楚这个归纳法证明的思路！你之前用反证法搞定了，现在卡在怎么“收缩”树来套归纳假设对吧？别慌，咱们一步步来拆解，保证你能明白。

首先先明确下定义：等双色树就是能做2着色（相邻顶点颜色绝对不同），而且两种颜色的顶点数量完全相等的树。

第一步：先搞定归纳的基例 #

归纳法得从最小的情况开始验证，等双色树的顶点数肯定是偶数（两种颜色数量相等嘛），最小的就是2个顶点的树——一条边连两个不同颜色的顶点，这俩都是叶子，红、蓝叶子各一个，完美符合命题，基例成立。

第二步：归纳假设 #

咱们先做个假设：所有顶点数为2k（k≥1）的等双色树，都至少有一个红色叶子和一个蓝色叶子。这一步是归纳法的核心前提，接下来就要用它推导出更大的树也满足命题。

第三步：归纳步骤（重点解决“收缩”问题） #

现在看顶点数为**2(k+1)**的等双色树T，我们要证明它也有红、蓝叶子各一个。这里的关键是通过“剪枝”得到符合归纳逻辑的小树，再反推回原树：

1. 先随便揪出T里的一个叶子v，假设它是红色的（颜色只是个名字，换成蓝色也一样），它的邻接点u肯定是蓝色的（因为2着色相邻不同色）。
2. 先看最简单的情况：如果u也是叶子，那直接就有红叶子v和蓝叶子u了，命题直接成立，不用往下走了。
3. 如果u不是叶子（说明u至少还有其他邻接点），那我们把叶子v从T里剪掉，得到一棵新树T'。这时候T'的顶点数是2(k+1)-1=2k+1，红色顶点少了1个（因为剪了v），所以红色有k个，蓝色还是k+1个——这时候T'不是等双色的，但没关系，我们可以用树的二分图性质来推导：
   • T'是树，也就是个二分图，其中蓝色顶点比红色多1个。这时候蓝色顶点里一定存在至少一个叶子——为啥？要是蓝色顶点个个度数都≥2，红色顶点个个度数≥1，那总度数会超过树的度数和（树的度数和是2*(顶点数-1)），而且这样的结构必然会出现环，和树无环的性质矛盾。
   • 这个蓝色叶子在原树T里也是叶子（我们只是剪了v，没碰它的邻接关系），再加上之前的红叶子v，这不就凑齐了两种颜色的叶子嘛！

这样一来，我们就用归纳假设推导出了更大的等双色树也满足命题，归纳步骤就完成了。

结合基例和归纳步骤，所有等双色树都至少有每种颜色的一个叶子，这个命题就证完啦！

备注：内容来源于stack exchange，提问作者Victor Feitosa