求教图论第二章课后习题答案！！

求教图论第二章课后习题答案！！

必要性显然，只证充分性。
用数学归纳法。
当 n=2 时，共有 2 个点，其度数：d1 + d2 = 2。
又因为 d1、d2 都是自然数，所以 d1 = d2 = 1，是个树。

假设 一共 n 个点，度数之和为：2(n-1)
由抽屉原则，至少有 1 个点度数为 1，设 d1 = 1
还是由抽屉原则，当 n>=3 时，至少有 1 个点度数为 2，设 d2 = 2
我们把 d1、d2 之间连一条边，然后考察剩下的顶点与度数的关系。
如果剩下的顶点与度数之间能构成树，那么再加上这条 d1 与 d2 之间的边，仍构成树。
剩下的顶点数：少了 d1 这个点，所以是 n-1 个顶点。
剩下的总度数：少了 2 度，所以是 2(n-1)-2 = 2(n-2)。
由归纳假设，剩下的可以构成树。
证完了。