离散数学 证明 证(1)→(2).若路径不惟一，必有回路. (2)→3).若G中有回路，则回路上任意两点之间的路径不 惟一.对n用归纳法证明n-1. 当=1时成立.设≤k时成立，证=k+1时也成立：任取 一条边e,G-e有且仅有两个连通分支G,G2.n≤k,由归 纳假设得m,=n-1,=1,2.于是， tFm1+m2+1=n1+n2-2+1=n-1. (3)=→(4).只需证明G连通.用反证法.否则G有s(s≥2)个连通 分支，它们都是树.于是，有m,=-1, m=∑m,=∑4-s=n-ss≥2) i=1 i= 这与n-1矛盾. 44 (3)(4). 只需证明G连通. 用反证法. 否则G有s(s2)个连通 分支, 它们都是树. 于是, 有mi=ni−1, 这与m=n−1矛盾. 证明 (2)(3). 若G中有回路，则回路上任意两点之间的路径不 惟一. 对n用归纳法证明m=n−1. 当n=1时成立. 设nk时成立，证n=k+1时也成立：任取 一条边e，G−e有且仅有两个连通分支G1 ,G2 . nik，由归 纳假设得mi=ni−1, i=1,2. 于是， m=m1+m2+1=n1+n2−2+1=n−1. ( 2) 1 1 =  =  − = −  = = m m n s n s s s i i s i i 证 (1)(2). 若路径不惟一, 必有回路