How many edges are needed to ensure k-connectivity?

Question

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

Answer 1

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.

Answer 2

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