the achievable maximum node-connectivity (κ) and maximum edge-connectivity (λ) that a simple graph G with n nodes with m edges can have are given by:
max κ(G) = max λ(G) = ⌊2m/n⌋
assuming n-1 ≤ m ≤ n(n-1)/2, which is necessary for a connected graph to exist.
Then the optimal connectivity can be achieved by the following construction:
- if m = n - 1
- then take any tree on n nodes
- otherwise:
- take a circle on n nodes
- set δ = ⌊2m/n⌋
- connect any 2 nodes that are within distance ⌊δ/2⌋ along the circle
- if not all nodes have degree ≥ δ, then pick a node with degree < δ, connect it to a node that is at distance ⌊n/2⌋ away along the circle. Repeat this until all nodes have degree δ, possibly with a single node that can have degree δ + 1