YLL討論網

想了很久還是不知從何下手的證明題:
Show that if a graph G has a Hamilton circuit, its line graph L(G) also has a Hamilton circuit.

我的想法是:
假設G有Hamilton circuit，同時該Hamilton circuit也是個Euler cycle，那這個問題就很簡單，因為Euler cycle會經過每個edge，而L(G)的每個vertex代表的都是G裡面的edge。只要循著G的Hamilton circuit路徑走，把每個edge轉換成vertex，每個vertex轉換成邊，就會形成L(G)裡的Hamilton circuit.
但是，Hamilton circuit並不一定是Euler cycle；倘若G有Hamilton circuit，經過了所有的vertex但並沒有經過所有的edge，那L(G)要如何經過它所有vertex(也就是G裡所有的edge)呢?

結論一：原圖 G 的 Hamilton circle 裡，任取兩個連續的邊：AB、BC，在 line graph L(G) 裡會形成兩個點，(AB) 與 (BC)。這是 line graph 定義。

結論二：依據 line graph 的基本性質，任何座標裡面包含同一個 X 的兩點，必互相通；所有座標裡面包含同一個 X 的所有點，將形成一個 complete graph。

結論三：由於 L(G) 裡面的 (AB) 與 (BC) 點都有 B 這個字，這兩點在 L(G) 裡面必相連通。

結論四：重複結論一的動作，將原圖 G 的 Hamilton circle 裡面所有的邊通通找出來，這將會在 line graph L(G) 裡面形成許多點。依據結論三， 這些點將形成一個圓；這裡稱作基礎圓。

結論五：原圖 G 中所有點的座標，將會在 L(G) 的基礎圓中出現正好兩次。因為基礎圓中的所有點，就代表了 G 的 Hamilton circle 的所有邊；可以說是 Hamilton circle 的 line graph。

結論六：原圖 G 中所有不包含於 Hamilton circle 的邊，在 L(G) 裡仍然會形成一個點。假設該點的第一個座摽為 X 。依據結論二，我們知道該點與所有座標包含 X 的點會形成一個 complete graph。

結論七：依據結論五，我們知道 X 這個座標值會在基礎圓裡出現兩次；也就是說基礎圓上有兩個點的座標都具有 X 。這兩個點與其他座標包含 X 的所有點，將會形成一個 complete graph。（參考結論二）

結論八：依據 complete graph 的基本性質，我們可以用基礎圓上面具有 X 座標的兩點當做起點與終點，做出一條走訪所有具有 X 座標的點的 Hamilton path。

結論九：利用結論八的模式，我們可以將基礎圓上的一條邊，延長成一個走訪所有 X 座標的點的 Hamilton path。而這些 paths，藉由基礎圓的架構，會連成一個 Hamilton circle。

得證。



看看怎樣用數學歸納法將上面九條換成數學語言吧。。。痛苦死了。