离散数学证明:证明有回路

Question

设G是n个点m条边的简单图，m≥n。证明：G中必有回路。
分别用反证法和其他方法证明

Answer 1

引自免费微信小程序：皆我百晓生

为了证明一个具有n个顶点和至少n条边的简单图G中必然存在回路，我们可以采用两种不同的方法：反证法和构造法。

方法一：反证法

我们首先假设图G中没有回路，即G是一个树形结构（因为树是没有回路的最简单的图）。对于任何树来说，它总是满足以下性质：在树中任意两个顶点之间只有一条路径，并且树的边数总是比顶点数少1，即对于一个有n个顶点的树，它的边数为n-1。

然而，题目中的图G有m条边，其中m ≥ n。根据我们的假设，G应该是一棵树，但这就导致了一个矛盾，因为m > n，这与树的定义相冲突。因此，我们的初始假设（图G中没有回路）是错误的，所以图G中必须存在至少一条回路。

方法二：构造法

另一种证明方法是通过构造出一个回路。由于图G有m条边，其中m ≥ n，我们可以按照以下步骤构建一个回路：

1. 从任何一个顶点v开始，选择一条连接到其他顶点的未访问过的边。
2. 沿着这条新边到达新的顶点w。
3. 重复上述步骤，每次选择一条未访问过的边，直到再次回到起点v。

这个过程一定能完成，因为我们最多会访问n个顶点，而图中有m条边，m ≥ n，这意味着总能找到一条未访问过的边。当我们返回起点时，就形成了一个回路。

综上所述，无论是通过反证法还是构造法，我们都得出了结论：对于一个有n个顶点和至少n条边的简单图G，必定存在至少一条回路。