Ensure weak connectivity in all k-out k-regular graphs depending on the number of vertices

If the graph were not weakly connected, there would have to be a connected component with at most $\lfloor \frac n2 \rfloor$ nodes. (If all components were larger than this, then since we have at least $2$ components, we'd end up with more than $n$ nodes total.)

In this component, each node can have edges to at most $\lfloor \frac n2 \rfloor - 1$ other nodes, so this can only happen (but can still happen!) when $k \le \lfloor \frac n2 \rfloor - 1$.

When $k \ge \lfloor \frac n2 \rfloor$, the graph is guaranteed to be weakly connected.


For the $2$-connected graph, I am assuming you still want weak connectivity. Here, suppose the graph is not $2$-connected: deleting some node $v$ disconnects the graph. Then $G-v$ has $n-1$ nodes, so there is a connected component with at most $\lfloor \frac {n-1}2 \rfloor$ nodes.

A node in that component of $G-v$ can have edges to at most $\lfloor \frac {n-1}2 \rfloor - 1$ other nodes in that component, but it can also have an edge to $v$. This can still happen when $k = \lfloor \frac {n-1}2 \rfloor$.

When $k \ge \lfloor \frac {n-1}2 \rfloor + 1$, the graph is guaranteed to be $2$-connected.

Similarly, when $k \ge \lfloor \frac {n-c+1}2 \rfloor + c -1$, the graph is guaranteed to be $c$-connected.