Let $k∈N$ and $G$ be a simple graph with $δ(G) = 2k$. Show that $G$ has a $(k + 1)$-edge-connected subgraph.
$δ(G)$ is defined as the minimum degree in the graph.
I thought about proceeding by induction on $k$ because I can see for a base case of $k=1$, the graph has every vertex of at least degree $2$, which means the graph is not a tree and thus contains a cycle. Cycles are always $2$-connected, so this cycle makes the desired $2$-edge-connected subgraph.
Then we assume the statement is true up to $k-1$ and show that it's true for $k$, but I don't see what to do next. And I'm not even sure if I did the right thing for the base case. How would I finish this proof? Or is there another/better way to do it without induction? Any help would be much appreciated.
We will prove the stronger result that if the sum of the degrees of the $n$ vertices of a simple graph is at least $2nk-2k+1$, then the graph has a $(k+1)$-edge-connected subgraph.
Consider such a graph and suppose it is not $(k+1)$-edge-connected. Then the vertices of the graph can be split into two subsets, $A$ and $B$, with at most $k$ edges connecting vertices of $A$ and vertices of $B$.
The sum of the degrees of vertices in at least one of $A$ and $B$, say $A$, must be at least $2mk-k+1$ where $m$ is the number of vertices in that subset. Deleting all the vertices of $B$ and the edges incident with these vertices then leaves a graph with $m$ vertices such that the sum of their degrees is at least $$(2mk-k+1)-k=2mk-2k+1.$$
The initial set up has now been reproduced in a subgraph with fewer vertices. This process cannot be continued indefinitely and so, at some point, we will obtain a subgraph which is $(k+1)$-edge-connected.