郭纪云

(海南大学信息科学技术学院，海南 海口 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－)，女，山东菏泽人，海南大学信息科学技术学院讲师，硕士.研究方向∶图论及其应用.