# How many edges are needed to ensure k-connectivity?

In this post, assume that all the graphs are simple (no loops or multiple edges allowed) for simplicity. I will use the notion of vertex-connectivity:

Definition. A graph $$G$$ is called $$k$$-connected, if removal of any fewer than $$k$$ vertices leaves $$G$$ connected.

Question. What is the minimal number $$f(n,k)$$ such that every simple graph $$G$$ on $$n$$ vertices and with at least $$f(n,k)$$ edges is $$k$$-connected?

For example, for $$k=1$$ (with 1-connected equivalent to connected) it is a standard exercise to show the following:

1. If $$G$$ is a graph on $$n$$ vertices such that $$G$$ has at least $$\frac{(n-1)(n-2)}{2}+1$$ edges, then $$G$$ must be connected. (for example, see this MSE post for a slight generalization).

2. There are graphs on $$n$$ vertices that have $$\frac{(n-1)(n-2)}{2}$$ edges that are not connected. For example, take the disjoint union of the complete graph $$K_{n-1}$$ and an isolated vertex.

Thus $$f(n,1)$$ is $$\frac{(n-1)(n-2)}{2}+1$$. What about $$f(n, 2)$$? Is there anything we can say about $$f(n, k)$$ for a general value of $$k$$?

The value of $$f(n,k)$$ is the expected $$\binom{n-1}{2} + k$$: the same as the number of edges that guarantees a minimum degree of $$k$$. In a graph with at least $$\binom{n-1}{2} + k$$ edges, there are at most $$n-1 -k$$ non-edges.

To prove that this is enough, we prove the contrapositive: suppose that a graph $$G$$ is not $$k$$-connected. Then there must be vertices $$v,w, x_1, x_2, \dots, x_{k-1}$$ such that in $$G - \{x_1,x_2, \dots, x_{k-1}\}$$, there is no path from $$v$$ to $$w$$.

In particular, this means that $$vw$$ is not an edge, and for every vertex $$y \notin \{v, w, x_1, \dots, x_{k-1}\}$$, either $$vy$$ or $$yw$$ is not an edge. That's $$1 + (n-k-1) = n-k$$ non-edges total. So this cannot happen if $$G$$ has at least $$\binom{n-1}{2} + k$$ edges.

To prove that this number is minimal, consider the graph consisting of $$K_{n-1}$$ and an $$n^{\text{th}}$$ vertex adjacent to $$k-1$$ others. This graph has $$\binom{n-1}2+k-1$$ edges, but is not $$k$$-connected, because deleting the $$k-1$$ neighbors of the last vertex will disconnect it.

• Misha, this is a wonderful answer. Thanks so much! Finally, I see Menger's theorem in action! – Prism Nov 9 '18 at 14:57

I just saw that I misread and answered a different question, I answered the minimum number $$m(n,k)$$ of edges that every $$k$$-connected graph on $$n$$ vertices has i.e., every graph on $$n$$ vertices w fewer than $$m(n,k)$$ edges is definitely not $$k$$-connected. My apologies OP. This may still be of interest though

Well, a trivial lower bound is $$\frac{kn}{2}$$ which is the number of edges in a $$k$$-regular graph on $$n$$ vertices (if $$G$$ is $$k$$-connected then every vertex must have degree $$k$$).

And in fact, the $$k$$-regular high-girth Ramanujan* graphs (for $$k=p^r+1$$ where $$p$$ is a prime $$p$$ may be 2) explicitly constructed, actually achieve that trival lower bound. Indeed, to show that a graph $$G$$ on $$n$$ vertices is $$k$$ connected, it suffices to show that $$G$$ has the following property: Every nonempty subset $$S$$ of $$V$$ with no more than $$\frac{n}{2}$$ vertices has at least $$k$$ neighbours in $$G$$ outside of $$S$$. [make sure you see why]. One can use the fact that $$G$$ has no small cycles (i.e., less than $$\log_{k-1} n$$ in length) to show that $$S$$ has at least $$k$$ neighbours outside of itself if $$1 \le |S| \le 8k$$ and $$n$$ is sufficiently large, and the 2nd eigenvalue method to show that $$S$$ has at least $$\min\{\frac{k|S|}{8}, \frac{n}{8}\}$$ neighbours outside of itself for $$S| \le \frac{n}{2}$$.

*The 2nd-largest eigenvalue of the adjacency matrix of a $$k$$-regular Ranaujan graph is at most $$2\sqrt{k-1}$$.

• That is okay. This is a cool answer! I didn't know the connection between the size of the 2nd largest eigenvalue and $k$-connectivity. – Prism Nov 9 '18 at 0:01
• The Harary graphs are a more general example; they achieve the lower bound $\lceil \frac{kn}{2}\rceil$ for all $n$ and $k$. – Misha Lavrov Nov 9 '18 at 14:41
• @Prism I am certain that "almost all" $k$-regular graphs are $k$-connected. Expanders (of which there are many explicit constructions in the literature and that are shown to be expanders via the size of the 2nd-largest eigenvalue, and if that isn't enough almost every $k$-regular graph is an expander and a pretty strong one at that) more than do the trick, sets $S$ w no more than half the vertices have $\Omega|S|$ neighbours outside of themselves in an expander, which is much larger than $k$ for all but very small $|S|$. Then small sets $S$ almost certainly have at least $k + |S|-1$ – Mike Nov 9 '18 at 16:11
• ....neighbours outside of themselves in random $k$-regular graphs, and for explicit constructions it is usually still easy to show that small sets $S$ have more than enough neighbours outside of themselves – Mike Nov 9 '18 at 16:13
• @MishaLavrov very nice reference! – Mike Nov 9 '18 at 16:13