# Minimum Number of Edges in $k$-connected Graph

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?

• The complete bipartite graph $K_{k,k}$ comes to mind, although obviously this requires $n=2k$. For larger $n$, maybe there is some way of increasing the part sizes while maintaining the $k$-connectivity. – Joffan Mar 13 '18 at 0:07

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$.