设nk时,结论成立。下证n=k+1时,结论 也成立。 设e=(u,是G中的一条边,由于G中无回 ’G1e(在G删除边所得的子图有两个连 所以 通分支G和G2,设它们的结点数和边数分别为 m1,n1和m2,n2。于是有n1k和n2k,由归纳 假设知 1和 则 m=m1+m2+1=n1-1+n2-1+1=n-1。设n≤k时，结论成立。下证n=k+1时，结论 也成立。 设e=(u,v)是G中的一条边，由于G中无回 路，所以 G-e(在G删除边e所得的子图)有两个连 通分支G1和G2，设它们的结点数和边数分别为： m1，n1和m2，n2。于是有n1≤k和n2≤k，由归纳 假设知：m1 =n1 –1和m2 =n2 -1，则： m=m1＋m2＋1=n1 -1＋n2 -1＋1=n-1