【正确答案】：证明:G=
已知:Δ(G)=6,δ(G)=5,则图中仅含度为5和度为6的顶点,即
n5+n6=l V l=9 (1)
反证,若n5≤5且n6≤4,由式(1)可知,等号必成立,即n5=5且n6=4
2×边数=5×n5+6×n6=5×5+6×4=25+24=49 (2)
式(2)的左侧为偶数,右侧为奇数,矛盾。故假设不成立,结论得证。 证毕
设无向简单图G= ,l V l=9,Δ(G)=6,δ(G)=5证明:G中至少有5个6度顶点或至少有6个5度顶点。
- 2024-08-04 00:04:15
- 离散数学(02324)
设无向简单图G= ,l V l=9,Δ(G)=6,δ(G)=5证明:G中至少有5个6度顶点或至少有6个5度顶点。
【正确答案】：证明:G= ,设度为6的顶点数为n6,度为5的顶点数为n5
已知:Δ(G)=6,δ(G)=5,则图中仅含度为5和度为6的顶点,即
n5+n6=l V l=9 (1)
反证,若n5≤5且n6≤4,由式(1)可知,等号必成立,即n5=5且n6=4
2×边数=5×n5+6×n6=5×5+6×4=25+24=49 (2)
式(2)的左侧为偶数,右侧为奇数,矛盾。故假设不成立,结论得证。 证毕
【正确答案】：证明:G=
已知:Δ(G)=6,δ(G)=5,则图中仅含度为5和度为6的顶点,即
n5+n6=l V l=9 (1)
反证,若n5≤5且n6≤4,由式(1)可知,等号必成立,即n5=5且n6=4
2×边数=5×n5+6×n6=5×5+6×4=25+24=49 (2)
式(2)的左侧为偶数,右侧为奇数,矛盾。故假设不成立,结论得证。 证毕
下一篇：下列选项中与题7图互为补图的是