无向图G=,且|V|=n,|e|=m,试证明以下两个命题是等价命题:G中每对顶点间具有唯一的通路,G

无向图G=,且|V|=n,|e|=m,试证明以下两个命题是等价命题:G中每对顶点间具有唯一的通路,G

G其实就是树.首先,如果G中每对顶点间具有唯一的通路,那么G当然是连通的.选取G的一个顶点,记为第1层顶点,所有和第一层顶点相邻的顶点记为第2层顶点,如此等等.主要到每个第n+1层的顶点都与一个第n层的顶点相邻并且不与任何其他的层数小于等于n的顶点相邻.否则,这个n+1层顶点与第一层顶点将有两条通路,矛盾.现在,第一层和第二层之间的边的数目就是第二层顶点的数目,第二层和第三层之间的边的数目就是第三层顶点的数目,如此等等.故n=m+1.另一方面,如果G连通且n=m+1.仍然借用上述操作：选取G的一个顶点,记为第1层顶点,所有和第一层顶点相邻的顶点记为第2层顶点,如此等等.但要加上这样一句：如果一个准备记为n+1层顶点的点已经和层数小于n的顶点相连,那么不标记它.然后,用G的边集e连结相邻两层的顶点(即如果某个n层顶点和某个n+1层顶点在G中相邻,则连结它).这样得到G的一个子图H,它的每两个点都有唯一通路且边数等于顶点数减1.这样,如果G还有除H的边集之外的边,那么G将有两个顶点,它们至少有两条通路,矛盾.

我也是这个答案