离散数学课后习题解析
1.证明：在任意一个含有n个结点的树中，存在n-1条边。
解答：
先根据树的定义，我们知道一棵树是一个连通无环的无向图，而一个无向图是有n个点，m条边的话，我们可以通过数学归纳法来证明。
基础情况：当树只有一个结点的时候，显然只有一条边。
归纳假设：对于任意一个有n个结点的树，它都包含n-1条边。
归纳步骤：现在我们要证明，对于任意一个有n+1个结点的树，它都包含n条边。
因为这棵树有n+1个结点，所以其中必定存在一个叶子结点。我们将这个叶子结点从树中删除掉，就得到了一棵只有n个结点的子树。根据归纳假设，这个子树中包含n-1条边。
现在我们把这个叶子结点重新加入树中，它必须连接到子树的某个结点上才能保证这棵树是连通的。这条新加的边使得树中的结点数增加了1，边数也增加了1。
因此，这棵有n+1个结点的树一共有n条边。
2.将40个分数排成两两相加的形式，一共有多少种结果？
解答：
首先，我们可以将40个分数看作40个点，在任意两个点之间连一条线段，表示将这两个分数相加。那么问题就转化成了求有多少种不同的连接方式。
根据组合学的知识，要求有多少种不同的连接方式，我们可以按照以下方式进行简化：
假设我们有n个点，我们要求它们组成的线段的种数。首先，从中挑选两个点，可以得到nC2种不同的选择方法。当我们确定了这两个点之间要连上线段后，问题就变成了把这两个点看做一个整体，和其它的n-2个点组成线段的种数。这个过程可以简化为有(n-2)+(1)个点，要组成线段的种数，即(n-1)个点组成线段的种数。我们可以用递归的方式计算出结果，即nC2*(n-1)。
而对于40个分数排成两两相加的形式的问题，我们可以套用上面的公式得到结果：
40C2*(40-1) = 38*40*20 = 30400
因此，一共有30400种不同的相加结果。
3.在一个无向图中，如果每个顶点的度数都不少于d，则这个图一定包含有一个长度不小于d+1的环。
解答：
我们可以按照以下方式来证明：
首先，我们可以使用数学归纳法来证明。
假设我们有一个无向图G，满足所有顶点的度数都不少于d。
基础情况：当d=1时，每个顶点的度数都不少于1，即每个顶点都至少与一个其它顶点相连，所以这个图一定包含有一个长度为2的环。
归纳假设：对于任意一个无向图G，如果每个顶点的度数都不少于d，则这个图一定包含有一个长度不小于d+1的环。
归纳步骤：现在我们要证明的是对于任意一个无向图G，如果每个顶点的度数都不少于d+1，则这个图一定包含有一个长度不小于d+2的环。
根据归纳假设，我们知道在一个度数不少于d的图中，一定包含有一个长度不小于d+1的环。现在我们在这个环中随意取一个顶点v，它的度数至少是d+1。
那么现在我们可以从这个顶点v开始遍历它的邻居节点，假设这些邻居节点为v1,v2,v3,...,vk。
因为每个节点的度数都不少于d+1，所以在这k个点中一定至少有一个点u与v相连，这样就形成了一个长度为3的环，即v->u->v1->v。
如果这k个点中有很多个点都与v相连，那么我们可以继续从这些点中随意挑选一个点w，重复上述过程，一定能够找到一个长度不小于d+2的环。
因此，如果一个无向图中每个顶点的度数都不少于d+1，则这个图一定包含有一个长度不小于d+2的环。
综上所述，我们可以证明在一个无向图中，如果每个顶点的度数都不少于d，则这个图一定包含有一个长度不小于d+1的环。
