Finding the number of edges $k$-connected graph with certain number of vertices

Question

I'm trying to figure out giving a $k$-connected graph how to find the number of edges needed for a certain number of vertices. For example, the number of edges in $2$-connected graph giving that it has $8$ vertices. I guess this is relevant to Menger's theorem.

Answer 1

You can do this directly if you take a look at a picture. It's easy to see the minimal number of vertices to gain a connected graph is $k-1$ just by chaining them in a straight line. Now each edge you add adds connectivity to both vertices to which it is connected, but it also clearly increases the connectivity to exactly two at a time, so with $8=2\cdot 4$ vertices you need at least $4$ more edges, however, if you look at the vertices in a line labeled $1-8$ from left to right, you can see that since $[i, i+1]$ is an edge for $1\le i\le 7$ then if you also use $[i, i+4]$ for $1\le i\le 4$ this gives each edge connectivity $2$ so we achieve the theoretical minimum of $11=8-1+ \lceil 8/2\rceil$.