证明的思路:只讨论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, 则相连. 假设从图中删除少于2r个顶点(构成子集V’), 图就 不连通了,删除后,顶点i,j属不同的分支. 考虑两个子集合(这里的序号对n 取模): S={i,i+1, …, j-1, j}; T={j, j+1, …, i-1, i}。 由于V’中总点数小于2r, 这两集合中至少有一个含V’ 中的点少于r 个,则此集合中删除V’后仍构成一 ij-通 路,矛盾