单顶点图是否满足欧拉图要求？关于欧拉回路添加边数命题的疑问

原命题回顾 #

设𝐺=(𝑉,𝐸)为无向连通图，𝑥为使𝐺添加边后存在欧拉回路所需添加的最少边数，𝑛为顶点数，则𝑥≤floor(𝑛/2)。

你的疑问解答 #

1. 单顶点图是否满足无向、连通的要求？ #

单顶点无向图完全满足：

• 无向性：无论是否带自环，单顶点图都属于无向图范畴，不存在有向边的限制。
• 连通性：连通图的定义是“任意两个不同顶点之间存在路径”，单顶点图没有两个不同顶点，该条件空真成立，因此属于连通图。

2. 带自环的单顶点图是否存在欧拉回路？ #

根据无向图欧拉回路的充要条件：图连通，且所有顶点的度数都是偶数。
单顶点带自环的图中，顶点度数为2（无向图中自环对顶点度数贡献2），是偶数；同时图连通，因此该图本身就存在欧拉回路——遍历自环即可形成起点和终点相同的回路，无需添加任何边，此时𝑥=0，和你提到的𝑥=1不符。

3. 你的例子修正与命题的验证 #

你可能混淆了原图的情况：若原图是单顶点无自环的图，此时需要分两种定义讨论：

• 若定义欧拉回路必须包含至少一条边：该图没有边，无法形成非空的欧拉回路，需要添加1个自环，此时𝑥=1，而floor(𝑛/2)=floor(1/2)=0，确实满足𝑥>floor(𝑛/2)，似乎推翻了命题。
• 若接受“空回路”作为欧拉回路（即没有边的单顶点图天然存在欧拉回路）：此时𝑥=0，符合命题结论。

需要注意：多数图论教材中，欧拉回路的定义隐含“遍历所有边”，对于无任何边的单顶点图，空遍历是否被认可存在争议。如果采用严格要求非空回路的定义，这个单顶点无自环的例子确实是命题的反例；但如果采用包含空回路的定义，该例子不成立。

另外，对于𝑛≥2的无向连通图，设奇度顶点的数量为𝑘（𝑘必为偶数），添加最少边数𝑥=𝑘/2即可让所有顶点度数为偶数（每添加一条边可消除两个奇度顶点）。而无向图中奇度顶点数量𝑘≤𝑛，因此𝑥=𝑘/2≤𝑛/2，又因为𝑥是整数，所以𝑥≤floor(𝑛/2)，这在𝑛≥2时是成立的。只有𝑛=1的极端情况会因定义差异出现矛盾。

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