[離散] Hamilton Paths and Cycles 一處證明
theorem: Let G = (V,E) be a loop-free graph with |V| = n >= 2.
If deg(x)+deg(y) >= n-1 for all x,y ε(屬於) V, x≠y,
then G has a Hamilton path.
proof:First we prove that G is connected. If not, let C1,C2 be two components
of G and let x,yεV with x a vertex in C1 and y a vertex in C2. Let Ci
have ni vertices,i = 1,2.Then deg(x) <= n1-1,deg(y) <= n2-1,
and deg(x)+deg(y) <= (n1+n2)-2 <= n-2, contradicting the condition
given in the theorem. Consequently, G is connected.
這只是前半段的證明,先證明G是connected,但
何以從命題以及前述得到黃色的那段Then? 資質駑鈍的我想了好久卻看不出端倪...
希望好心人能幫我解惑
在此先獻上十二萬分的感謝!
(DISCRETE and COMBINATORIAL MATHEMATICS by Ralph P. Grimaldi 5th Ed p.560)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.194.107
※ 編輯: gentlefaith 來自: 114.44.194.107 (01/09 07:45)
推
01/09 09:13, , 1F
01/09 09:13, 1F
→
01/09 09:14, , 2F
01/09 09:14, 2F
→
01/09 12:47, , 3F
01/09 12:47, 3F