Let $k > 2$ and let G be a graph with $|G| = n \geq 2k − 1$. Prove that if $e(G) \geq (2k − 3)(n − k + 1) + 1$ then $G$ contains a subgraph $H$ such that $H$ is $k$-connected.
Note a graph $G$ is $k$-connected if
$1)$ $|G|\geq k+1$
$2)$ No set of at most $k-1$ vertices disconnects $G$
My idea is to remove the vertex of least degree at each step and use induction. However, in general, I don't feel comfortable with the definition of $k$-connectedness, so here goes:
The base case $k=3$ is trivial as then $G$ turns out to be $K_5$ and $K_5$ is $3$-connected (it is actually even $4$-connected)
For the inductive step (backward induction), we have that we can remove some edges (it will make the problem tougher) so that we can assume that $e(G)=(2k − 1)(n − k ) + 1$. Hence the minimal degree will be less than $\frac{2e(G)}{n}$ So after removing a vertex $v$ of minimal degree we have at least $((2k − 1)(n − k ) + 1)\frac{n-2}{n}$ edges
But then as $((2k − 1)(n − k) + 1)\frac{n-2}{n} \geq (2k − 3)(n − k + 1) + 1$
Hence in the graph with the vertex $v$ removed we have that we can find a $(k-1)$-connected graph.
I tried to then join this vertex of least degree to the found subgraph, but failed to finish the argument.
Would be very grateful if anyone could assist me and also if you could provide me with some insight on the $k$-connectedness
As is noted in the comments, your argument doesn't give a proper proof of the base case since if $k = 3$ you only know that $n \geq 5$ not that $n = 5$. In fact, as far as I can tell this really is a problem.
Because of this issue, I think it's simpler to use induction on $n$. So we fix $k > 2$ and first let $n = 2k-1$.
As you noted, we can assume without loss of generality that $e(G) = (2k-3)(n-k+1)+1 = k(2k-3) + 1 = \frac{(2k-1)(2k-2)}{2} = \binom{n}{2}$. So $G = K_n \supseteq K_{k+1}$ and hence $G$ certainly has a $k$-connected subgraph.
Now, for the induction step, suppose the claim holds for all graphs $G$ with $|G| = n \geq 2k-1$ and consider the case $|G| = n+1$. If $G$ has a vertex of degree less than $2k-3$ then we can apply the induction hypothesis to the graph obtained by removing this vertex from $G$. So we just want to show that there is such a vertex. For a contradiction, suppose instead that $\delta(G) > 2k-3$ and $G$ has no $k$-connected subgraph.
In particular, $G$ is itself not $k$-connected so, by Menger's theorem, we can find $X \subseteq G$ such that $|X|<k$ and $G \setminus X$ has two components whose vertex sets are $V_1$ and $V_2$ respectively. Let $G_i = G[V_i \cup X]$ be the graph with vertex set $V_i \cup X$ whose edges are the ones appearing between the relevant vertices in $G$.
If $v \in V_i$, then $v$ has at least $2k-2$ neighbours in $G_i$ and hence $|G_i| \geq 2k-1$. Hence, we can apply the induction hypothesis to $G_i$. If $G_i$ contains a $k$-connected subgraph so does $G$ and we are done. Otherwise, by the induction hypothesis, $e(G_i) \leq (2k-3)(|G_i| - k + 1)$.
Notice that every edge of $G$ appears in at least one of the $G_i$ so this leads us to \begin{align*} e(G) \leq& e(G_1) + e(G_2) \\ \leq& (2k-3)(|G_1| + |G_2| - 2k + 2) \end{align*} Now $|G_1 \cap G_2| = |X| \leq k-1$ so $|G_1| + |G_2| = |G| + |G_1 \cap G_2| \leq n + k - 1$. All in all we then have, $$e(G) \leq (2k-3)(n-k+1).$$ This contradicts our original assumption, so $G$ must have a vertex of degree at most $2k-3$ and we are done.