②→④ 先证G中无回路。若G中存在某个结点上的 自回路,Vu∈V,由条件知到w存在一条路L1 u.,因为ν上有自回路,所以u到存在另一条 路L2:u.w,这与G中每一对结点之间存在惟 的路矛盾。若G中存在长度大于等于2的一条回路 则回路上两个结点之间存在不同的路。这与条件 是矛盾的。所以G中无回路。 以下用归纳法证明m=n-1。 当n=1时,G为平凡图,m=0=1-1=n-1。结 论成立。 设n时,结论成立。下证n=k+1时,结论也②③ 先证G中无回路。若G中存在某个结点v上的 自回路，uV，由条件知u到v存在一条路L1： u…v，因为v上有自回路，所以u到v存在另一条 路L2：u…vv，这与G中每一对结点之间存在惟一 的路矛盾。若G中存在长度大于等于2的一条回路， 则回路上两个结点之间存在不同的路。这与条件 是矛盾的。所以G中无回路。 以下用归纳法证明m=n–1。 当n=1时，G为平凡图，m=0=1–1=n–1。结 论成立。 设n≤k时，结论成立。下证n=k+1时，结论也 成立