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

设无向图G中有n个结点,n-1条边,用归纳法于n,证明G是连通图则G中无回路.
设无向图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)+……+(xk-1)=n-k条边,少于已知的n-1条边,所以假设不成立,该无环图一定是联通的.