Assume that we have a connected graph with $n$ vertices and each vertex with a minimum degree of $\frac{n-1}{2}$. And let $m$ be the minimum degree of the graph. Prove that by removing less than $m$ edges from the graph, it's still connected.
Somehow I believe that this question is proved somewhere here, but I couldn't find it, sorry if it's a duplicate.
I've nearly solved this question by using contradiction, and proving that there is no cut vertex, so we have to remove the required edges from one vertex and then, that vertex still has an edge to be connected to rest of the graph and the rest of the graph is connected itself.
but I want a better and neater solution, if anyone can help me, I'll appreciate it, thanks.
Best Answer
Suppose we can delete $r<m$ edges (color them red) so that $G$ becomes unconnected with components $A,B$. We can assume that $|A|\geq |B|=:b$ so $b\leq {n\over 2}$
Redelete this red edges for a time.
Take any $v$ in $B$. Vertex $v$ is connected with at most $b-1$ vertices in $B$, so it must be connected with at least $d_v-(b-1)$ vertices in $A$. Say $B= \{v_1,v_2,...v_b\}$ so we have at least $$\Big(d_1-(b-1)\Big)+\Big(d_2-(b-1)\Big)+...+\Big(d_b-(b-1)\Big)$$ edges from $B$ to $A$ so they are all red. Thus we have $$r\geq b\cdot m -b(b-1)$$ Since we supposed $r<m$ we have now $$m>bm-b(b-1)\implies b>m \;\;\;{\rm and}\;\;\;b\ne 1$$
So we have $${n\over 2}\geq b\geq m+1 \geq{n-1\over 2}+1={n+1\over 2}$$ a contradiction.