Let k be a given positive integer to determine the required connectivity of a graph. Let G be a weighted graph. Determine a minimum-weight k-connected spanning subgraph of G.
If k=1, this problem reduces to find a minimum spanning tree. Kruskal’s algorithm can be applied to find such a tree.
However if k is greater than one, then the above problem becomes difficult and unsolvable. Only if G is a complete graph in which each edge is assigned unit weight, then the problem has a simple solution. It is an m-connected graph H(m,n) on n vertexes and the structure of H(m,n) depends on the parities of m and n; three cases can be considered
Case 1: if m=even, let m=2r, then H(2r,n) is constructed as follows. It has vertexes 0, 1, …, n-1 and two vertexes i and j are joined if i-r<=j<=(i+r)mod(n).
Case 2: if m=odd, and n=even, let m=2r+1, then H(2r+1,n) is constructed by first drawing H(2r,n) and then adding edges joining vertex i to vertex i+(n/2) for 1<=i<=n/2.
Case 3: if m=odd, n=odd, let m=2r+1, then H(2r+1,n) is constructed by first drawing H(2r,n) and then adding edges joining vertex 0 to vertex (n-1)/2 and (n+1)/2 and vertex i to vertex i+(n+1)/2 for 1<=i<=(n-1)/2.
Theorem (Harary Theorem): The graph H(m,n) is m-connected.