第3题

设 $G$ 连通但既非完全图、也非圈、也非树；那么 $G$ 含有一个圈，但它本身不是那个圈。取一个最短圈 $C_0$。若 $G$ 不含三角形，选取 $C_0$ 外部与 $C_0$ 上某点 $a$ 相邻的顶点 $b$（因为 $G$ 连通且比 $C_0$ 大，此点存在），并设 $c$ 是 $C_0$ 上与 $a$ 相邻的一个顶点；由 $C_0$ 的最短性可知 $b$ 与 $c$ 不相邻，于是在 $a,b,c$ 处的切换是合法的，并且它保持图连通，因为 $a$ 仍保留圈上另一个相邻顶点，而 $b$ 通过新边与 $c$ 重新相连。若 $G$ 含有三角形，取一个极大完全子图 $K$（是顶点集的真子集）以及一条从 $a\in K$ 到某个 $b\notin K$ 的边；由极大性可知存在 $c\in K$ 与 $b$ 不相邻，于是在 $a,b,c$ 处的切换是合法的并保持图连通，因为 $a$ 仍与 $K$ 的其余部分相连，而 $b$ 通过 $c$ 重新相连。