每棵非平凡树至少有两片叶子的证法研究*

郭纪云

(海南大学信息科学技术学院，海南 海口 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度……