图论技术问询：G的补图连通性及2-连通图等价性证明请求

让我来一步步拆解这两个图论问题，用易懂的方式给出证明和说明：

一、非完全简单图的补图是连通的 #

首先要明确前提：这里的图G是非完全的简单图（完全图的补图是空图，显然不连通）。下面是补图$\overline{G}$连通的说明：

任取补图里的两个不同顶点u和v：

• 如果u和v在原图G中不相邻，那它们在补图$\overline{G}$里直接有边相连，显然存在路径；
• 如果u和v在原图G中是相邻的，因为G不是完全图，所以一定存在第三个顶点w，w至少和u、v中的一个不相邻（不然G就是完全图了）。假设w和u不相邻，那在补图里u-w-v就是一条连接u和v的路径；如果w和v不相邻，同理u-w-v也是有效路径。

不管哪种情况，补图里任意两个顶点都能找到路径相连，所以补图$\overline{G}$是连通的。

二、简单图G是2-连通的充要条件证明 #

我们要证的是：简单图G是2-连通的，当且仅当对于任意三个不同的顶点x、y、z，G中存在一条经过y的简单x-z路径。

必要性（2-连通 ⇒ 满足路径条件） #

如果G是2-连通的，意味着G没有割点，而且任意两个顶点之间至少有两条内部不相交的简单路径。现在任取三个不同顶点x、y、z：

• 先看x和z，它们之间至少有两条内部不相交的路径P和Q。如果y在P或者Q上，那这条路径就是经过y的x-z路径，直接满足条件；
• 如果y不在P和Q上，因为G没有割点，y到路径P上的某个非x/z顶点a有一条路径，到路径Q上的某个非x/z顶点b也有一条路径。把这些路径拼接起来：x→...→a→y→b→...→z，这就是一条经过y的x-z简单路径。

充分性（满足路径条件 ⇒ 2-连通） #

我们分两步证：

1. G是连通的：任取两个不同顶点x和z，随便找第三个顶点y（因为2-连通图至少有3个顶点），根据条件存在经过y的x-z路径，所以x和z必然连通，整个图G是连通的。
2. G没有割点：用反证法，假设G有割点v，去掉v后G会分成至少两个不连通的分支，比如A和B。取a∈A，b∈B，现在考虑三元组(a, b, v)——这是三个不同的顶点，根据条件应该存在一条经过b的简单a-v路径。但a在A，b在B，去掉v后A和B不连通，所以a到b的路径必须经过v，那这条“经过b的a-v路径”就会变成a→...→v→...→b→v，这就重复了顶点v，不是简单路径，和条件矛盾。所以G不存在割点。

结合连通性和无割点，G就是2-连通的。

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