设G是有n个结点,n条边的简单连通图,且G中存在度数为3的结点.证明：G中至少存在有一个度数为1的结点.
题目
设G是有n个结点,n条边的简单连通图,且G中存在度数为3的结点.证明：G中至少存在有一个度数为1的结点.
答案
反证法.假设G中不存在度数为1的结点,G是连通图,所以G的结点的度数至少是2.
G有3度节点,所以G的所有结点的度数之和大于等于2(n-1)+3=2n+1.
而G有n条边,度数之和是2n.
矛盾.
所以G中至少存在有一个度数为1的结点.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
- 1、Tongtong was born in 1994.Thatwas the year of _______.
- 我的老师作文,要小标题,500字!好的追分.
- 汉译英：我吃了些药,但是没起作用.I （）some medicine,but it （）（）.
- 一个圆柱形容器,底面半径10cm,里面盛有不满的水,现将一个底面积为157平方厘米的圆锥形铁块浸没在容器内
- Jalan Law Yew Swee是马来西亚,吉隆坡的什么地方?
- 写出下面命题的逆命题,并判断真假 1、同位角相等,两直线平行； 2、内错角相等,两直线平行
- 小明用一个木块分别在一块木板、一条毛巾上做关于滑动摩擦力的实验，实验用到的器材还有弹簧测力计和一个钩码，如图所示．图中数字表示实验序号． 实验序号 弹簧测力计读数（N） 1 1
- 2道汉译英,不要电子翻译
- thank you ( ) ( )me about ( )谢谢你告诉我关于你的情况
- 某同学质量为60kg,他住在一栋高楼中,放学回家时从一层乘电梯回家,电梯匀加速上升,经过4s速度达到2m/s
热门考点
- 梯形的中位线长m厘米，下底为a厘米，那么上底长是_厘米．
- 已知在三角形ABC中,AD是BC边上的高,M是BC上的中点,DM=1|2AB,求证角B=2角C
- they should encourage those among us who cannot swim five yards.这里encourage后面怎么能接those,
- 从“2、3、4、5、6、7”中任选三个数字,组成带分数（也是最简分数）.可以组成几个这样的带分数?
- 1mol葡萄糖水解生成ATP多少?
- 已知两曲线y=x^3+ax和y=x^2+bx+c都经过点p（1,2）,且在点p处有公切线,求a,b,c的值
- 理想电压源内阻为0,理想电流源的内阻为无穷大对不对
- 修改病句 在防非典的日子里,投入到抗击非典的斗争之中.
- 以“开始”为话题,写一篇作文（或给点提示也OK）SOS~
- 核酸是什么构成,有几种,真核细胞与原核细胞的区别是?