如何证明有n个点n-1条边的无向连通图一定是一颗树（即没有回环）

如题，想不到方法证明。。。。。。

用扩大路径法,随意选取一个点,每需和其他一个点连接需要至少一条边,因为他是连通图,所以至少有N-1条边,只有N-1条边的时候每条边都是桥所以可知他就是一棵树

将 所以 树枝末端的 “点边”去除， 直到找不到树枝为止(去除的 点 和 边数量相等). 此时 要么剩下一点，要么剩下回环（即，无枝）。 若剩下一点， 则n点n-1个边。 若剩下一环，则n点 n 个边。 术语不会。。。。

请问是数学还是物理： n个顶点的连通图 生成的树的边有?条

因为是无向连通图，所以存在一棵生成树，它是这个无向连通图的子图，含有无向连通图的全部顶点（n个）以及n-1条边。换句话说。一个连通图的生成树就是该连通图擦掉若干条边后的一个子图。 上面是铺垫，下面用反证法证明： 证明：首先可知连通图必含生成树，下面证明只有n个顶点和n-1条边的连通图本身就是一棵树。 由于无向连通图本身只有n个顶点和n-1条边，又一定存在生成树，如果无向图本身不是一棵生成树（假设），那么它就需要擦去若干条边。由于擦去任意一条边后的图一定没有生成树，因为边的个数不足以拥有生成树这个子图（因为生成树至少需要n-1条边），说明该无向连通图没有生成树（本身不是，擦去后又不存在），这与无向连通图必有生成树矛盾，所以可知假设错误，该无向图本身一定是一棵生成树。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息