设 G 是一个有 n 个顶点的图，其中没有一个是孤立的，并且有 n-1 条边，其中 n ≥ 2。证明 G 至少包含两个 1 次顶点。
我已经通过使用属性总和度数 = 2|E|尝试了这个问题 . 这个问题可以用鸽子洞原理解决吗？
问问题
115 次
1 回答
1
我想不出用鸽子洞原理解决这个问题的明智方法，我会这样做：
度数之和 = 2n - 2 = 2|E|
由于没有顶点可以被隔离，所有顶点的度数必须至少为 1，因此有 n - 2 个“备用”边端要附加。n-2 个东西可以放入 n 个位置意味着至少 2 个必须留空（这类似于鸽洞原理，但有点相反），因此至少 2 个顶点的度数必须为 1。
我认为你最好在这里问这种问题：https ://math.stackexchange.com/
于 2012-05-29T07:43:45.063 回答