question about constructive proof of a certain type of graph

Question

I want to prove that I can always construct a graph in the following way: For all $n$ and $k>0$, we can build a graph with $n$ vertices and $k \cdot n$ edges, that cannot be disconnected by removing at most $2k-1$ vertices.

Answer 1

Consider the circulant graph with lengths $1,2,\dots, k$ and $n$ vertices ($n\geq 2k+1$).

If we color $2k-1$ vertices red and the rest blue then the blue vertices are connected.

proof: Suppose not, notice that the connected components are not intertwined, so we label them $C_1,C_2,\dots$ in clockwise order.

Now notice that between the last element of $C_i$ and the first of $C_{i+1}$ (in clockwise order) there are at least $n$ red vertices.

This guarantees at least $2k$ red vertices