graph - 二部连通图证明

Question

一位朋友向我提出了一个看似正确的猜想，但我们俩都无法提出证明。这是问题所在：

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

证明 U 中至少有一个顶点的度数高于 V 中的 1 是微不足道的，但要证明存在一对存在连接它们的边却难倒我们。

Answer 1

对于具有 a∈U 和 b∈V 的任何边 e=(a,b)，令 w(e)=1/deg(b)-1/deg(a)。对于任何顶点 x，与 x 入射的所有边上的 1/deg(x) 之和等于 1，因为存在 deg(x) 这样的边。因此，所有边 e 上的 w(e) 之和等于 |V|-|U|。由于|V|-|U|>0，对于某个边e=(a,b)，w(e)>0，这意味着deg(a)>deg(b)。

Answer 2

通过反证法证明，即假设deg(a) ≤ deg(b) ∀(a,b)∈E，其中E是图的边集（约定第一个元素在U中，第二个在V）。

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

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中的所有节点，因此根据我们的假设，我们必须有

∑<sub>a∈U deg(a) ≤ ∑<sub>b∈V(F) deg(b)

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

∑<sub>a∈U deg(a) < ∑<sub>b∈V deg(b)

这是不可能的；这应该是二分图的等式。