二分图连通性证明

Question

一个朋友给我提出了一个猜想，似乎是正确的，但我们都无法证明。这里是问题：

给定一个连通的二分图，具有不相交的非空顶点集U和V，使得|U|＜|V|，所有顶点都在U或V中，并且没有连接同一集合中两个顶点的边，则存在至少一条连接U中的顶点a和V中的顶点b的边，使得degree(a)＞degree(b)。

证明至少存在一个度数高于V中度数为1的U中顶点很容易，但是证明存在一对具有连接它们的边的顶点却困扰着我们。

- Joe Kelley

---

这个陈述是微不足道的错误（因为你可以选择 U 为空）。您的 U 和 V 是否应该覆盖图形，并且没有内部边缘？ - user97370

是的，抱歉，U和V是使图形二分的集合。它们包含所有顶点，没有内部边缘。我进行了编辑以使其更清晰。 - Joe Kelley

Answer 1

对于任意一条边 e=(a,b)，其中 a∈U，b∈V，令 w(e)=1/deg(b)-1/deg(a)。对于任意一个顶点 x，所有与 x 相关的边的 1/deg(x) 的总和等于 1，因为有 deg(x) 条这样的边。因此，所有边的 w(e) 总和等于 |V|-|U|。由于 |V|-|U|>0，所以存在某条边 e=(a,b)，使得 w(e)>0，这意味着 deg(a)>deg(b)。

- Pontus von Brömssen

Answer 2

采用反证法证明，即假设对于图的边集E中的任意一对顶点(a,b)，都有deg(a) ≤ deg(b)，其中约定第一个元素在U中，第二个元素在V中。

对于F⊆E，定义可通过边集F到达的子集V(F)，即：

V(F) = { b | (a,b)∈F }

现在按照以下方式构建边集F：

F = empty set
For a ∈ U:
    add any edge (a,b)∈E to F
Keep adding arbitrary edges (a,b)∈E to F until |V(F)| = |U|

得到的集合 V(F) 与所有节点在 U 上相连，因此根据我们的假设，必须满足

∑_a∈U deg(a) ≤ ∑_b∈V(F) deg(b)

然而，由于 |U|=|V(F)| 和 |U|<|V|，我们知道必须至少有一个“未连接”的节点 v∈V\V(F)，并且由于图是连通的，所以 deg(v)>0，因此我们得到

∑_a∈U deg(a) < ∑_b∈V deg(b)

这是不可能的；对于二分图，应该是一个等式。

- mitchus