1
$\begingroup$

So I know $G$ is connected since $\delta(G)\geq(n-1)/2$, we can simply prove it by contradiction. My approach to this question is use contradiction. Suppose that $G$ is not $\frac{n - 1}{2}$- edge - connected, then let $W$ be a edge set s.t $G\setminus W$ is disconnected. Then there will be at least 2 component and the vertex $v$ in a smaller component will have a degree $\leq n/2 - 1$ if $v$ is not incident to any edge in $W$. This will contradict the assumption. However, I don't know how to continue the case when all vertex is incident to $W$.

$\endgroup$
0
$\begingroup$

Let $V’$ be the set of t the vertices in the smaller component and $|V|=k\le n/2$ vertices. Then each vertex $v\in V’$ is adjacent only to vertices of $V’$, than is degree of $v$ in the residual graph is at most $k-1$. Therefore at least $\delta(G)-(k-1)\ge (n+1)/2-k$ edges incident to $v$ belong to $W$, that is $$|W|\ge k((n+1)/2-k)\ge (n-1)/2.$$

$\endgroup$

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.