设G是有n个结点、n+1条边的图，且每个结点的度数都不超过3，证明：G中至少有2个度数等于3的结点。

设G是有n个结点、n+1条边的图，且每个结点的度数都不超过3，证明：G中至少有2个度数等于3的结点。

证明：假设G中度数为3的结点最多1个。
由于G的每个结点的度数都不超过3，所以C的结点度数总和最多为2（n-1）+3=2n+1。
另一方面，由于C有n + 1条边，所以C的结点度数总和为2n + 2。
而2n+2≤2n + 1是不可能的，因此假设不成立，
所以G中至少有2个度数等于3的结点。