Edge-Connectivity of a graph

Question

If $G$ is a graph of order $n$ such that $\delta(G) \geq (n-1)/2$, then $\lambda(G)= \delta(G)$

So I know this statement to be true. How would I prove this statement?

Answer 1

This solution is probably much longer than needed, the inequalities I am using might be improved on...

The inequality $\lambda(G) \leq \delta(G)$ is well known and trivial.

Assume now by contradiction that

$$\lambda(G) < \delta(G) \,.$$

This means that we can disconnect the graph by removing $\delta(G)-1$ edges, lets call them $v_1,..,v_k$ where $k=\Lambda(G)$.

Then one of the components of the graph has $l \leq \frac{n}{2}$ vertices. Originally, the total degree of the vertices in this component were at least $l \frac{n-1}{2}$. As we removed $k$ edges, the total degree is at least $$l \frac{n-1}{2}-2k \,.$$

As this component has $l$ vertices, the total degree is at most $\frac{l(l-1)}{2}$.

Thus we have $$l \frac{n-1}{2}-2k \leq \frac{l(l-1)}{2} \,.$$

Now using $k \leq l-1$ we get

$$l(n-1) \leq 4k+ l(l-1) \leq 4(l-1)+l(l-1)=(l+4)(l-1) < l(l+4)$$

Thus

$$n-1 < l+4 \,.$$

Now, using $l \leq \frac{n}{2}$ you get

$$n-1 < \frac{n}{2} +4 $$

This yields $$n < 10 \,.$$

The cases $n \leq 9$ can now be studied now $n$ by $n$. Note that if $n$ is even, $\delta(G) \geq (n-1)/2$ can be replaced by $\delta(G) \geq (n-2)/2$; while if $n$ is odd we have $l \leq \frac{n-1}{2}$. If you study separately these two cases, you get sharper inequalities in the proof, I would expect to go down to something like $n \leq 5$.

Answer 2

Since $G$ is a graph of order $n$ such that $\delta(G)\geq(n-1)/2$, then $G$ is connected. Also, for every graph $G$, $\lambda(G)\leq\delta(G)$. Assume that $\lambda(G)\lt\delta(G)$. Let $X$ be a minimum edge-cut of $G$ where $|X|=\lambda(G)$. Then $G-X$ is disconnected by definition. However, since $\lambda(G)\lt\delta(G)$ we know that $G-X$ is connected which is a contradiction. Thus $\lambda(G)=\delta(G)$.