3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Prism Nov 9 '18 at 0:01
  • 1
    $\begingroup$ The Harary graphs are a more general example; they achieve the lower bound $\lceil \frac{kn}{2}\rceil$ for all $n$ and $k$. $\endgroup$ – Misha Lavrov Nov 9 '18 at 14:41
  • $\begingroup$ @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$ $\endgroup$ – Mike Nov 9 '18 at 16:11
  • $\begingroup$ ....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 $\endgroup$ – Mike Nov 9 '18 at 16:13
  • $\begingroup$ @MishaLavrov very nice reference! $\endgroup$ – Mike Nov 9 '18 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.