每棵非平凡樹至少有兩片葉子的證法研究*

郭紀云

(海南大學信息科學技術學院，海南 海口 570228)

每棵非平凡樹至少有兩片葉子的證法研究*

郭紀云

(海南大學信息科學技術學院，海南 海口 570228)

采用七種方法證明了每棵非平凡樹至少有兩片葉子，從而為相關內容的研究提供了很好的理論參考.

圖;樹;葉子;度

樹是無圈的連通圖，葉子(或1度點)是指度為1的頂點.只有一個頂點的圖稱為平凡圖，其他所有的圖都稱為非平凡圖.既沒有環也沒有重邊的圖稱為簡單圖，也叫單圖.本文所涉及到的圖都是非平凡圖，并且都是有限的簡單圖.

引理 1［1，2］若 δ(G) ≥ 2，則 G 中含有圈.

證 設P是圖G中的一條最長路，u是P的一個端點.由于d(u)≥δ≥2，故存在一頂點w∈V，使得邊uw與P相交，不然P就不是最長路了.故圖G中含有圈.

引理2［3，4］若圖 G是 Δ ≥ k的樹，則 G至少有 k片葉子.

定理［5，6］每棵非平凡樹至少有兩片葉子.

這是一個較為簡單的命題，其證法頗多，現將它們詳細地總結出來，以期對讀者有所幫助.

證法1 設G是任意一棵非平凡樹，則對?v∈V，有d(v) ≥1，由度和公式得若 ?v∈ V，有d(v) ≥2，則矛盾.若存在唯一的頂點 v∈ V，使得 d(v)=1，則1=2V－1，也矛盾.故每棵非平凡樹至少有兩片葉子.

證法2 設G是任意一棵非平凡樹，并設G中共有x片葉子，則 2ε =又因為ε=V－1，從而可得x≥2.故G中至少有兩片葉子.

證法3 若對?u∈V，d(u)=2，則G是Euler圖，從而含有Euler閉跡.由于Euler閉跡可以表示成若干個圈的并，故G中有圈，這與樹的定義相矛盾.現設G中僅有一個1度點，有k個度大于等于3的奇度點，則2(V－1)=1+2(V－k－1)+3k，得到k≤－1＜0.由于奇度點的個數必為偶數，所以k必為正奇數，矛盾.假設不成立，故G中至少有2個1度點.

以上三種證法雖然思路各不相同，但都基于同一個重要定理──握手定理(即度和公式).由此可見，握手定理作為圖論第一定理，其地位和作用更加凸顯.

證法4 事實上，若非平凡樹的(u，v)－路的起點或終點的度大于1，這時因樹無圈，易知(u，v)－路可繼續延長.故非平凡樹中的最長路的起點和終點的度必為1.

證法5 若δ(G)≥2，由引理1知G中含有圈，這和G是樹不含圈矛盾.故G中至少存在一個頂點u，使得d(u)=1，在G中由u出發的(u，v) －路，若d(v)＞1，顯然(u，v) －路可繼續延伸，由于G中不含圈，這種路的延伸永遠不會停止，但這又和G是有限圖相矛盾，故G中除u外至少還存在一個頂點的度亦為1.

證法6 對V使用數學歸納法.當V=2時，G=K2，結論顯然成立.假設V≤k－1時結論成立，則當V=k(＞2)時，由于Δ≥2，所以由引理2知，頂點數V=k(＞2)的圖至少有2片葉子.故命題成立.

證法7 對V使用數學歸納法.當V=2時，由證法6知結論已成立.假設V≤k－1時結論成立.現設G是任意一棵具有k(＞2)個頂點的樹，由證法5知G中至少存在一個頂點u，使得d(u)=1，下證G'=G－u是一棵具有V－1個頂點的樹.由于一個度為1的頂點不屬于任何一條連接其他兩個頂點的路.因此，對于w，v∈V(G')，G中每條 (w，v) －路都是G'中的路.因此G'亦是連通的，由于刪除一個頂點不會產生一個圈，因此G'亦是無圈的.所以G'是一棵具有V－1個頂點的樹，從而G中至少有2片葉子.

“數學是思維的體操.”發展思維是提高學生素質的重要方面.而一題多解可以啟動學生的求異思維，加深學生對所學知識的深刻理解，訓練學生對數學思維和數學方法的嫻熟運用，鍛煉學生思維的廣闊性和深刻性、靈活性和獨創性，從而培養學生的思維品質，發展學生的創造性思維.

［1］Bondy J，Murty U S R.Graph Theory with Applications［M］.New York:Elsevier North Holl，Inc，1979.

［2］Bollobas B.Graph Theory:An Introductory Course［M］.New York:Springer－ verlag，Inc，1979.

［3］張先迪，李正良.圖論及其應用［M］.北京:高等教育出版社，2005.

［4］孫惠泉.圖論及其應用［M］.北京:科學出版社，2008.

［5］盧開澄，盧華明.圖論及其應用［M］.北京:清華大學出版社，1995.

［6］王朝瑞.圖論［M］.北京:北京理工大學出版社，2001.

(責任編校:晴川)

O157.5

A

1008－4681(2011)05－0006－01

2011－07－14

郭紀云(1984－)，女，山東菏澤人，海南大學信息科學技術學院講師，碩士.研究方向∶圖論及其應用.