# Prove that $G$ is $k$-edge-connected.

Let $G$ be an $n$-vertex graph with minimum degree $k$ that contains at least $\binom{n-k-1}{2}+\binom{k+1}{2}+k$ edges. Prove that $G$ is $k$-edge-connected.

A disconnected graph on $n$ vertices with no components of size less than $k$ has at most $\binom{n-k}{2}+\binom{k}{2}$ edges.

Can I use this result replacing $k$ by $k+1$ ?

Suppose $G$ is not $k$-edge connected, then suppose the minimum number of edges required to disconnect $G$ be $m$, of course, $m<k$, so after removing $m$ edges from $G$, the graph becomes disconnected. Let this disconnected graph be $H$.

Also now the disconnected graph $H$ has $\binom{n-k-1}{2}+\binom{k+1}{2}+(k-m)$ edges, hence by the result you proved it must contain a component $M$ of size less than $(k+1)$, say it's size is $p$, where $1\leq p\leq k$.

Hence degree of each vertex in that component $M$ of $H$ is at most $p-1$, whereas the degree of each vertex of $M$ in the original graph $G$ was at least $k$.

Note that if there was an edge $e$ between any two vertices $u$, $v$ of $M$ in the original graph $G$, that edge was not removed to get $H$, as the graph $M$ is connected, removing that edge $e$ would not help to disconnect $G$, In other words if $e$ does not belong to the edge set of $H$, then if we add $e$ to $H$, the new graph would still be disconnected, hence contradicting the minimality of $m$.

Hence at least $(k-(p-1))\times p$ edges has been removed from the orginal graph $G$.

Now $[(k-(p-1))\times p]-k=kp-k-p^2+p=(k-p)(p-1) \geq 0$.

Hence $(k-(p-1))\times p\geq k$.

But we know we have removed $m$ edges from the original graph $G$ to obtain $H$ and $m<k$, hence a contradiction.

So we have proved that $G$ is $k$-edge connected.