求证：当图G的最小度δ(G)≥n/2时，边连通度κ′(G)=δ(G)（反证法思路求助）

我来帮你把这个反证法的思路理清楚，咱们一步步拆解推导：

首先明确反证的核心逻辑：我们要证明的结论是当图G的最小度δ(G)≥n/2时，它的边连通度κ′(G)等于δ(G)。那反证的话，我们先假设这个结论不成立——也就是同时存在两个条件：

• κ′(G) < δ(G)
• δ(G) ≥ n/2

接下来我们借助几个关键定义和定理来推矛盾：

1. 设X是G的最小边割，也就是X的大小|X|正好等于κ′(G)（这是边连通度的定义：最小的边割的大小）。去掉X之后，G会被分成两个互不连通的子图G₁和G₂（这里可以补充下：最小边割对应的分图一定是两个，要是分成更多子图，那其中某个子图和其他部分的边割大小会比X更小，就和X是最小边割矛盾了）。
2. 根据鸽巢原理，G₁和G₂中至少有一个的顶点数不超过⌊n/2⌋，我们不妨假设G₁的顶点数|V(G₁)|≤⌊n/2⌋（反正两个子图对称，选哪个都不影响推导，这就是WLOG「不失一般性」的意思）。

现在重点来了，我们从G₁内部的顶点度数入手找矛盾：

• 对于G₁中的任意一个顶点v，它在原图G中的度数deg(v)≥δ(G)≥n/2（这是最小度的定义）。
• 但v在G₁内部最多只能连到|V(G₁)|-1个顶点（因为G₁总共就这么多顶点），所以v连向G₂的边数至少是deg(v) - (|V(G₁)|-1) ≥ δ(G) - (|V(G₁)|-1)。

我们把G₁中所有顶点连向G₂的边数加起来，这个总和正好就是|X|（因为X就是G₁和G₂之间的所有边）。那可以得到不等式：
$$|X| \geq |V(G₁)| \cdot \left(δ(G) - |V(G₁)| + 1\right)$$

现在结合我们的假设|X|=κ′(G)<δ(G)，把这个代入进去：
$$|V(G₁)| \cdot \left(δ(G) - |V(G₁)| + 1\right) < δ(G)$$

我们把这个不等式整理一下：
$$|V(G₁)| \cdot δ(G) - |V(G₁)| \cdot (|V(G₁)| - 1) < δ(G)$$
$$δ(G) \cdot (|V(G₁)| - 1) < |V(G₁)| \cdot (|V(G₁)| - 1)$$

这里分两种情况讨论：

• 如果|V(G₁)|>1：那|V(G₁)|-1>0，两边可以同时除以这个正数，得到δ(G) < |V(G₁)|。但我们之前假设|V(G₁)|≤⌊n/2⌋≤n/2，而δ(G)≥n/2，这就出现了**δ(G) < |V(G₁)| ≤n/2 ≤δ(G)**的矛盾！
• 如果|V(G₁)|=1：也就是G₁是单个顶点v，那v的所有边都属于X，所以deg(v)=|X|。但deg(v)≥δ(G)，而|X|=κ′(G)<δ(G)，这也直接矛盾了！

两种情况都推出了矛盾，说明我们最开始的假设「κ′(G)<δ(G)」是不成立的。那结合边连通度的基本性质（κ′(G)≤δ(G)是恒成立的，因为每个顶点的所有边就是一个边割），就可以得出κ′(G)=δ(G)，原命题得证。

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