(3)→(4):在T是连通图,且e=n-的条件下, 证明T是无回路图且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通,只能是下图 显然T是无回路的。(3)→(4):在T是连通图,且e=n-1的条件下, 证明T是无回路图,且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通, 只能是下图 显然T是无回路的