习 题 2
1． 证明：非平凡树的最长路的起点和终点均是 1 度的。
证明：设
T
为非平凡树且
P
是
T
的最长路。若
P
的一个端点
u
不是一度点，即
() 2du
，则除了
P
上的邻点外，
u
还有一个邻点
v
。若
()vVP
，则
P
加上点
v
后到一条
更长的路，这与
P
是最长路矛盾；若
()vVP
，则得到一个圈，这与
T
是树矛盾！证毕。
2． 证明：每棵恰有两个 1 度顶点的树均是路。
证明：设
T
为恰有两个 1 度点的树。若
T
不是路，则
T
至少存在一个度不小于 3 的点，
其余顶点的度均不小于 2。由握手引理有，
()
2()322(3)212(1)
uVT
mdu n nn
，
矛盾。因此
T
是路。证毕。
3． 若
G
是树且
k
，则
G
至少有
k
个 1 度顶点。
证明：若不然，设
G
至多有
1k
个 1 度顶点。由于
k
，于是，由握手定理得：
()
2() () 1 2( ) 2 1 2 2
vVG
mG dv k k n k n n
。即
1mn
，这与树的定义矛盾。证
毕。
4． 证明：若
G
是森林且恰有 k2 个奇度点，则在
G
中有 k 条边不重的路
12
,,,PP
k
P
使得
12
() () ( ) ( )
k
E
GEPEP EP
证明：对
k
进行归纳。当
1k
时，
G
恰有两个奇度点，此时，由练习 2 可知，
G
是一
条路。假设当
kt
时，结论成立。令
1kt
。在
G
的一个分支中取两个 1 度顶点
u
与
v
，
令
P
是连接
u
与
v
的唯一路，则
()GEP
是有
2t
个奇度点的森林，由归纳假设，它可以分
解为
t
条边不重合路之并，所以
G
可以分解为
1t
条边不重合路之并。证毕。
5． 证明：正整数序列
12
(, , , )
k
dd d
是一棵树的度序列当且仅当
1
1
2( 1)
n
i
dn
。
证明：必要性显然，故仅证明充分性。对
n
作数学归纳。当
1n
和 2 时，结论显然成
立。假设当
nk
时，结论成立。令
1nk
。首先, 序列中至少有一个数为 1，否则，序列
的和大于
2k
，与条件矛盾！所以，
1
1
k
d
。我们从序列中删去
1
d
和
1k
d
，增加数
1
*1dd
并将其放在它应该在的位置（按从大到小排列）。得到新序列
1
S
。该序列含
k
个数，且序列
和为
2( 1)k
, 由归纳假设，存在树
1
T
，它的度序列为
1
S
。现在，增加点
v
，把它和
1
T
的点
*d
连一条边后得到树
T
。树
T
即为所求。证毕。
6． 设
T
是有
1k
个顶点的任意一棵树。证明：若
G
是简单图且
k
，则
G
有一个
子图同构于
T
。
证明：对
k
进行归纳。当
1k
时，结论显然成立。假设当
1kn
(
2n
)时结论成
资源评论
