[Math] Minimum Number of Edges in $k$-connected Graph

connectednessgraph theory

Since $\delta(G) \ge \kappa(G) \ge k$, we can see that:
$$ |E(G)| \ge \frac{n \delta(G)}{2} \ge \frac{nk}{2} $$
Is this the best bound possible?

For $k = 4$, the answer to another question suggests that a cycle with an extra edge connecting each vertex with the vertex two away clockwise is a $4$-connected graph with $\frac{4n}{2} = 2n$ edges. It seems you can generalize that example to all $k$ even. Is there an example of a $k$-connected graph with $\frac{nk}{2}$ edges when $k$ is odd?

Best Answer

The Harary graphs $H_{k,n}$ are the generalization of your construction to arbitrary $n$ and $k$.

For all $n$ and $k$, we place $n$ vertices around a circle, and then:

  • Join each vertex to the $\lfloor \frac k2 \rfloor$ vertices closest to it in either direction.
  • If $k$ is odd and $n$ is even, join each vertex to the vertex directly opposite it in the circle.
  • If $k$ is odd and $n$ is odd, number the vertices $0, 1, \dots, n-1$, and connect vertex $i$ to vertex $i + \frac{n-1}{2}$ for $0 \le i \le \frac{n-1}{2}$.

The result is a $k$-connected graph on $n$ vertices with the minimum possible number of edges: $\lceil \frac{kn}{2} \rceil$.

Related Question