Question

设图g有k个连通分支,q(G)>p(G)-k,证明G含有圈

Answer 1

问：设图g有k个连通分支,q(G)>p(G)-k,证明G含有圈

答：按照k-连通的定义,只需要证明在G中删除任意k-1个顶点后,所得宴轮戚到的图仍是连晌陵通的.你自己可以验证一下,删掉k-1个点之后,所得到图的最小度≥（p-k+1）/2,这个新图的顶点数为p-k,显桐镇然是连通的.

问：有没有具体步骤

答：按照k-连通的定义，只需要证宴埋芹明在G中删除任意k-1个顶点后，所得到的图仍是连通的。你自己可以验证一下，删掉k-1个点之后，所得到图的最小晌毕度≥（p-k+1）/2，这个新图的顶点数为p-k，显然液老是连通的。