设G是有n个结点、n条边的简单连通图，且G中存在度数为3的结点。证明：G中至少有一个度数为1的结点。

设G是有n个结点、n条边的简单连通图，且G中存在度数为3的结点。
证明：G中至少有一个度数为1的结点。
【正确答案】：假设G中不存在度数为1的结点，由于G是连通图，所以C的每个结点的度数≥2。
G有n个结点，且有一个度数为3的结点，所以G的结点度数总和至少为2（n-1）+3 =2n + 1。
另一方面，由于G有n条边，所以C的结点度数总和为2n。而2n≥2n+ 1是不可能的，因此假设为谬。
所以G中至少有一个度数为1的结点。