设无向图G中有n个结点,n-1条边,用归纳法于n,证明G是连通图则G中无回路.

题目

设无向图G中有n个结点,n-1条边,用归纳法于n,证明G是连通图则G中无回路.

答案

假设这个无环图是不连通的,则设图G有k个连通分支G1,G2,…,Gk（k≥2）,设G1有x1个结点,G2有x2个结点,G3有x3个结点……Gk有xk个结点,则有x1+x2+x3+……+xk=n,又因为Gi有xi-1条边,所以图G有(x1-1)+(x2-1)+(x3-1)+……+(...