(1)(2)
如果G 是树,则G 中任意两个顶点之间存在唯一的路径。
存在性。
由 G的连通性及定理14.5 的推论(在n 阶图 G中,若从顶点v
i
到v
j
(v
i
v
j
)存在通路,则 v
i
到v
j
一定存在长度小于等于n-1 的初级通路( 路径) )可知,
u,v∈V, u与 v 之间存在路径。
唯一性(反证法)。
若路径不是唯一的,设Г
1
与Г
2
都是u 到v 的路径,
易知必存在由Г
1
和Г
2
上的边构成的回路,
这与G 中无回路矛盾。
第 4 页 / 共 41 页