Question

一道离散数学题

设 n 阶无向树 G = <V , E> 中有 m 条边，证明：m = n - 1

Answer 1

对n使用数学归纳法。当n=1时结论显然成立。假设n>=2且n-1阶无向树恰有n-2条边。
首先，对于n>=2阶无向树G，每个节点的度数均>=1，由于G中不含有圈，由定理*知必存在一个节点v，其度数为1.
考虑G-{v},由于G是不含圈的连通图且deg(v)=1，所以G-{v}是不含圈的连通图，即G-{v}是n-1阶无向树，他恰有n-2条边。因此G恰有n-1条边。
定理*：在无向图G=（V，E）中，若任意v属于V，有deg（v）>=2，则G中存在圈。
参考资料：邓辉文《离散数学（第三版）》P119.