题目

1. 证明: $n$个结点的图$G$是树当且仅当$G$为有$n-1$条边的连通图.
2. 证明: $n$个结点的图$G$是树当且仅当$G$为有$n-1$条边的无圈图.

解答

1. 必要性:

   先证明$n$个结点的树必有$n-1$条边.

   利用数学归纳法, 当$n=1,2,3$时, 结论显然成立, 设当$n=k$$(k>3)$时结论成立, 即$k$个结点的树有$k-1$条边, 只需证$n=k+1$时结论成立.

   由于非平凡树至少有两个叶结点，设$v$是其中一个，删除$v$以及与之关联的边, 这时新的树有$k$个顶点, 根据归纳假设知该树有$k-1$条边, 此时加入刚才去掉的结点和边, 得到的树有$k+1$个结点和$(k-1)+1=k$条边, 假设成立, 证毕.

   根据树的定义得到树为连通图.

   充分性:

   反证, 假设$G$不是树, 则$G$含有至少一个圈, 移除圈中的一条边, 这在$n$个顶点上留下一个具有$n-2$条边的连通图, 然而这是不可能的, 因为$n$顶点的连通图至少要有$n-1$条边.

2. 必要性: 由树的定义显然得到.

   充分性: 只需证明满足条件的图连通即可.

   利用数学归纳法, 当$n=1,2$, 连通性显然成立, 假设当$n=k$时, $k-1$条边的图为连通图.

   考虑$k+1$个结点, $k$条边的无圈图$G$, 该图至少有一个结点的度为 1.

   首先, 由于$k$条边的图其度的总和为$2k$, 因为有$k+1$个结点, 所以至少有一个结点的度$<2$, 否则度的总和将$\geqslant2k+2$. 并且不存在度为$0$的点, 因为如果存在, 将有一个连通分量有$n$个结点和$n$条边, 这将形成一个圈, 与条件矛盾.

   现在去掉该度为 1 的结点及与之相关联的边, 得到的图有$k$个结点和$k-1$条边, 由归纳假设, 新得到的图是连通图, 此时添加上之前删掉的边和结点, 得到的图仍然是连通的, 于是假设成立, 证毕.