Graph Theory: Connectivity I got this problem on a Graph theory PDF, but I can not answer it.
Prove that if G is a graph such that $d(G)\ge n/2$, then $\lambda (G)=d(G)$ (where $d(G)$ stands for the minimum degree of the graph, $n$ is the number of vertices, and $\lambda(G)$ is the edge connectivity).
Thanks!  
 A: First, observe that $\lambda(G)\leq d(G)$ (verify this!). Then the question is really how to show that $d(G)\leq \lambda(G)$.
Remember that $\lambda(G)$ means the least number of edges needed to delete from $G$ to disconnect it. When you disconnect a graph with a minimal number of edges, what you really do is partition the vertices into two nonempty blocks $B_1,B_2$, and delete all edges with one endpoint in $B_1$, and the other endpoint in $B_2$. Then you want to show that for any such pair $B_1,B_2$, the number of edges with an endpoint in each is at least $d(G)$.
How many edges between $B_1$ and $B_2$ are there? First, let's assume without loss of generality that $B_2\leq B_1$. Note that this means $|B_2|\leq \frac{n}{2}\leq |B_1|$. Let $b=|B_2|$. To bound the number of edges between $B_1$ and $B_2$, you should find the minimum number of edges with at least one endpoint in $B_2$, the maximum number of edges with both endpoints in $B_2$, and take their difference. You should then be able to show that the resulting difference is at least $d(G)$. I'll leave it here for now and let you try to work out the solution, but I'll give some hints for each step.
Hint $1$: To count the minimum number of edges with at least one endpoint in $B_2$, use $d(G)$.
EDIT: Looking back, this hint was not as clear as it could have been- $bd(G)$ will count some of the edges between $B_1$ and $B_2$, and some edges with both endpoints in $B_2$. However, the edges with both endpoints in $B_2$ can be counted twice- once for each endpoint. You'll need to subtract the number found in hint $2$ twice.
Hint $2$: To count the maximum number of edges with both endpoints in $B_2$, use binomial coefficients, if you're familiar with the concept.
Hint $3$: To show that the difference between those two values is at least $d(G)$, you can rewrite it as $d(G)+x$, for some expression $x$, and can show that $x\geq 0$ using the fact that $d(G)\geq \frac{n}{2}$.
