图论证明题
设9阶无向图的每个顶点的度数为5或6,证明它至少有5个6度顶点或者至少有6个5度顶点.
人气:182 ℃ 时间:2020-01-30 00:57:59
解答
设有a个6度点,则有9-a个5度点,6a+5(9-a)=2倍的边数,故a为奇数,a<5则a至多为3,即有
至少有6个5度顶点
推荐
- 离散数学图论证明
- N个城市间有K条相互连接的真达公路.证明:当K>(N-1)(N-2)/2时,人们便能通过这些公路在任何两个城市间旅行.
- 什么情况下完全图Kn中包含一个欧拉回路,说明理由.
- 有N个点,度数分别为d1,d2,d3.dN,并且其和为2N-2,证明存在度数分别为d1,d2...dN的树.
- 图论的
- 已知等差数列{an}的前n项的和为sn,且a1+a3+a5=105,a2+a4+a6=99,则sn取得最大值时的n=_.
- 在平行四边形ABCD中,对角线AC⊥BD于点O,AB=AC=2,则BD等于几?
- 焊接符号一个,
猜你喜欢