当前位置：首页 >
离散数学(02324) > 正文内容
设图G有n个结点，n条边，且存在度数为1的结点。
证明：G中至少有一个结点度数≥3。
设图G有n个结点，n条边，且存在度数为1的结点。
证明：G中至少有一个结点度数≥3。
假设G中不存在度数≥3的结点，则C的每个结点的度数最多为2。（2分）
G有n个结点，且有一个度数为1的结点，所以G的结点度数总和最多为2（n-1）+1= 2n-1。
另一方面，由于G有n条边，所以C的结点度数总和为2n。（2分）
而2n≤2n-1是不可能的，因此假设为谬。所以G中存在度数≥3的结点。（1分）
扫描二维码免费使用微信小程序搜题/刷题/查看解析。
版权声明：本文由翰林刷题小程序授权发布，如需转载请注明出处。