西安电子科技大学$6.7.1 无向树软件学院（3）连通且m=n-1。（4）无简单回路，但增加任一新边，得到一条(3) -(4)且仅一条简单回路。首先，证明T中无简单回路，对结点数n进行归纳。+当-1时，m-n-1-0，显然无简单回路。假设当r-k-1时T中无简单回路，现考察当n-k时的情况。此时T中至少有一个结点v的度数为1，因为若k个结点的度数均大于等于2，则T中的边数将不小于k，这与m-n-1矛盾。现将一个度为1的结点v及其关联的一条边从T中删除，得到一个含k-1个结点的图T-V。根据归纳有T-v中无简单回路，再将v及其关联的一条边放回，恢复图T，T也必无简单回路。+其次，证明增加任一新边(И，)得到一个且仅一个基本回路。由于图T是连通的，从到v有一条基本路径P，这条基本路径P与(Vi）就构成了一条简单回路。假设增加边（，）后得到不止一个基本回路，这说明从到vi还有与P不同的另外一条基本路径P，那么P与P将构成的回路中必包含简单回路。这与T中无简单回路矛盾。所以树中无简单回路，但增加任一新边，得到一条且仅一条基本回路。+西安电子科技大学 §6.7.1 无向树 软件学院 （3）连通且m=n-1。 （4）无简单回路，但增加任一新边，得到一条 且仅一条简单回路