证明：G连通不含回路推出G无回路且n=m+1
问题描述：
证明：G连通不含回路推出G无回路且n=m+1
答
无回路不用证,用数学归纳法证明n=m+1当n=2时,m=1,所以n=m+1成立假设当n小于等于k时,n=m+1成立当n=k+1时,由于没有回路,去掉任一边e后,G将变成两个连通支,记为G1,G2G1,G2中的结点数均小于等于k,所以满足假设,有n1=m1+1...相反呢 谢谢假设G不连通,则G至少有两个连通支记为G1,G2由于n=m+1所以至少有一个连通支,不妨设为G1,满足n小于等于m,所以G1中有回路亦即G中有回路,矛盾所以G连通