Question

若无向图G中恰有两个奇数度的结点,则这两结点间必有一条路。

Answer 1

【答案】：设图G的两个奇数度结点为v₁和v₂,从v₁开始构造一条迹,即从功出发经关联于v₁的边e₁到达结点u₁,若deg(u₁)为偶数,则必有不同于e₁的边e₂与u₁关联,经e₂到达结点u₂,如此继续下去，每边取一次,直到另一个奇度结点停止,因为G中只有两个奇度结点,故该结点只能是v₁和v₂中的一个,若该结点是v₂,则从v₁和v₂的一条路就构造好了;若该结点仍是v₁,则此路为闭迹，由于闭迹上每个结点都关联偶数条边，而deg(u)为奇数,所以至少有一条关联于功的边不在此闭迹上,继续从功出发,沿该边到达另一结点u'1,依次进行下去,直到另一个奇度结点停下,这样经有限次后必可到达结点v₂,此即为一条从v₁和v₂的路。
注:本题所用知识点:迹的概念及有关性质