求度数为r、顶点数n=3r的正则图G无桥的证明提示

我来给你梳理几个实用的证明思路，核心都围绕反证法展开——这也是图论里处理这类存在性问题的经典手法：

思路1：从连通分支的度数矛盾入手 #

• 先假设图G存在一条桥e，把e去掉之后，G会被拆成两个互不连通的子图G₁和G₂。设G₁有k个顶点，那G₂的顶点数就是3r - k。
• 回忆图论的基本性质：任何图的总度数都是偶数（因为每条边给两个顶点各贡献1度，总度数是边数的2倍）。对于r正则图G来说，总度数是3r × r = 3r²，显然是偶数。
• 看子图G₁：它内部的边贡献的度数和是偶数，但桥e给G₁中的一个顶点贡献了1度。而G₁中每个顶点在原G中的度数都是r，所以G₁的总度数（原G中的度数）是k × r，这个值等于G₁内部边的度数和加上1。由此可得k × r必须是奇数（偶数+1=奇数），这意味着k和r都得是奇数（只有奇数×奇数才会是奇数）。
• 再看G₂：同理，它的总度数（原G中的度数）是(3r - k) × r。按照刚才的逻辑，这个值也得是奇数，但3r是奇数×奇数=奇数，减去k（奇数）得到的是偶数，偶数×r（奇数）结果是偶数，这就和“必须是奇数”的结论矛盾了！
• 矛盾说明最初的假设不成立，所以G不存在桥。

思路2：从分支内部的度数和规则推导 #

• 同样先假设存在桥e，拆出G₁和G₂两个分支。
• 在G₁中，除了和桥相连的那个顶点，其他所有顶点在G₁内部的度数都是r；而那个和桥相连的顶点，在G₁内部的度数是r - 1（因为原本的r度里有1度来自桥，去掉桥后就剩r-1度）。
• 计算G₁内部的总度数：(k - 1) × r + (r - 1) = k×r -1。但根据图的基本性质，任何图的内部总度数必须是偶数（每条边贡献2度），所以k×r -1是偶数 → k×r是奇数，这同样推出k和r都是奇数。
• 再看G₂：它的内部总度数是(3r - k)×r -1，代入k是奇数、r是奇数的条件，3r -k是偶数，偶数×r是偶数，偶数减1是奇数，这和“内部总度数必须是偶数”的规则矛盾。
• 矛盾再次证明假设错误，G没有桥。

内容的提问来源于stack exchange，提问作者user529756