证明：若无向图G中每个顶点的度至少为2，则G必然存在回路。

[问答题]

牛客4414733号

因为每个结点的度至少为2，则说明没有度为0和度为1的结点，所以该图存在回路。

发表于 2017-11-30 21:25:31 回复(0)

xizhou

简单的说,就是没有回路,必有叶子节点,与度不为1矛盾
复杂的说：
反证：如果G中不存在回路,则必有一个节点的度为1
可以说明：任意找一个节点,开始遍历,那么最终会访问到一个叶子节点.
任何一个访问到的节点u,存在以下几种情况
1. 是叶子节点（证明结束）
2. 存在节点v,v尚未被访问,且边(u,v)存在,则继续访问v
3. 任何与u有边相连的节点都已经被访问,这种情况会构成回路（与假设矛盾,证明结束）
因为节点个数有限,所以只有有限次可能会落入情况2,随着遍历的进行,必然会落入情况1和3

发表于 2021-12-11 20:00:23 回复(0)