问答题
证明:除平凡树外,树都不是哈密顿图.
【正确答案】
若T是2阶树,同构意义下,T为K
2
,K
2
显然不是哈密顿图.
为了证明n(n≥3)阶树不是哈密顿图,先证明下面命题.
命题 在无向树T中,非树叶顶点都是割点.
证明 只有阶数n≥3的树中才有非树叶顶点.设u为T中非树叶顶点,u与v和ω相邻,设e
1
=(v,u),e
2
=(u,ω).则e
1
,e
2
均为桥,于是p(T-u)≥2,故u为割点.
由此命题可知,阶数n≥3的树T中有割点,由定理的推论可知,T不是哈密顿图.
【答案解析】
提交答案
关闭