Prove that for every graph G(V,E) such that: $$ \delta(G)\ge\frac{|V|}{2} \Rightarrow k_e(G)=\delta(G) $$ (where $\delta(G)$ = minimum degree of vertex in a graph, $k_e(G)$ = edge connectivity of a graph)
I know that $k_e(G)$ can't be greater than the minimum degree of a graph, but I have no idea how to prove it isn't less than $\delta$. How should I proceed? Is there any "intuitive" way of approach?
As you noticed, the hard part is proving that $k_e (G) \geq \delta (G)$.
Let $A \sqcup B$ be a non-trivial partition of the vertex set of $G$, with $N := |A| \leq |B|$. Then there are at least $N \delta (G) - N(N-1)$ edges between $A$ and $B$, the lower bond being reached if and only if the subgraph $A$ is complete.
A quick study of this function should tell you for which value of $N$ this is minimal ($1 \leq N \leq |V|/2$), using the assumption on $\delta (G)$. Then, you'll see that you always need to delete at least $\delta (G)$ edges to disconnect $A$ and $B$.