证明的思路：只讨论k为偶数 L.前已说明：含n个顶点的k-连通图至少有nk/2条边 以这一较简单 2.左边的解恰好是nk/2条边 的情况为例 3.因此，只须证明，这图是k一连通的 令=2r(r是整数) Harary的解法实际上是对任意顶点i,让它与满足下 述条件的顶点j相连： ≥(i-r)modn或j(i+r)mod n 于是，如果两点取模差不大于r,则相连 假设从图中删除少于2个顶点（构成子集”），图就 不连通了，删除后，顶点，属不同的分支 考虑两个子集合这里的序号对n取模)： Hk.n S={i,计1，.，-1，}；T=j,jt1,…,i-1,i}。 k,n均是偶数 由于P中总点数小于2r,这两集合中至少有一个含 中的点少于r个，则此集合中删除心后仍构成一通 路，矛盾。证明的思路：只讨论k为偶数 Hk,n k,n均是偶数 以这一较简单 的情况为例 1. 前已说明：含n个顶点的k-连通图至少有nk/2条边 2. 左边的解恰好是nk/2条边 3. 因此，只须证明，这图是k－连通的． 0 1 2 3 7 6 5 4 令k=2r (r是整数) Harary的解法实际上是对任意顶点i, 让它与满足下 述条件的顶点j 相连： j(i-r) mod n 或 j(i+r) mod n 于是，如果两点取模差不大于r, 则相连． 假设从图中删除少于２r个顶点（构成子集V’）, 图就 不连通了，删除后，顶点i,j属不同的分支． 考虑两个子集合(这里的序号对n 取模)： S={i,i+1, …, j-1, j}; T={j, j+1, …, i-1, i}。 由于V’中总点数小于2r, 这两集合中至少有一个含V’ 中的点少于r 个，则此集合中删除V’后仍构成一 ij-通 路，矛盾