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.

I had already proved that;

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.