Proof of the number of edges required to disconnect a graph
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.
$\endgroup$ 12 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$I'm not quite sure about your attempt; you seem to be implying that the smallest edge-cut (set of edges which disconnects a graph) are all of the edges incident with a single vertex. In practise, this is usually not the case (in fact, the difference between the size of a minimum edge-cut and the minimum vertex degree in a graph may be made arbitrarily large). I'm going to present a proof of your fact here that is not the most direct proof, but which exposes you to some must-know terminology and basic results in connectivity theory.
Defintions. Let $G$ be a simple graph of order $n$. $e(G)$ denotes the size (number of edges) of $G$. $\delta(G)$ denotes the minimum degree of $G$. $\kappa'(G)$ denotes the edge-connectivity of $G$, i.e. the minimum number of edges required to disconnect $G$ (when removed). When $\emptyset \neq S \subset V(G)$, an edge cut $[S, \overline{S}]$ is the set of all edges which have one endpoint in $S$ and the other in $\overline{S}$ (note that removing any set of edges of the form $[S, \overline{S}]$ necessarily disconnects the graph).
Lemma. Let $\emptyset \neq S \subset V(G)$. If $\vert [S, \overline{S}] \vert < \delta(G)$, then $\vert S \vert > \delta(G)$.
Pf sketch. First, note that we can count $\vert [S, \overline{S}] \vert$ directly as $$\vert [S, \overline{S}] \vert = \sum_{v \in S}deg(v) - 2e(G[S])$$ (verify this; the proof is very short, just count the contributions to $\sum_{v \in S}deg(v)$ from each of $G[S]$ and $[S, \overline{S}]$ (these are all of the contributions)). Now, using the hypotheses along with the fact that $2e(G[S]) \leq \vert S \vert (\vert S \vert - 1)$, we obtain $$\delta(G) > \vert S \vert\delta(G) - \vert S \vert (\vert S \vert - 1),$$ (again, verify that you can obtain this inequality), which in turn implies that $\vert S \vert > \delta(G)$ (we're using that $S$ is nonempty here as not to have a division-by-zero issue), as desired. $\square$
Proposition. If $G$ is a graph of order $n$ with $\delta(G) \geq \frac{n-1}{2}$, then $\kappa'(G) = \delta(G)$.
Proof. Let $G$ be a graph of order $n$ satisfying $\delta(G) \geq \frac{n-1}{2}$. Suppose, for the sake of contradiction, that $\kappa'(G) < \delta(G)$ (we can't have $\kappa'(G) > \delta(G)$ due to Whitney's theorem), and let $[S, \overline{S}]$ be a minimum edge cut. By the above lemma, the components of $G - S$ contain more than $\delta(G)$ vertices. Using the hypothesis that $\delta(G) \geq \frac{n-1}{2}$, we immediately obtain $$n \geq 2(\frac{n-1}{2} + 1) = n + 1,$$ a clear contradiction. Hence $\kappa'(G) = \delta(G)$. $\square$
This, of course, completes your question, since it says that you must remove at least $\delta(G)$ vertices to disconnect the graph (so removing fewer than $\delta(G)$ edges (no matter which edges you choose) will not disconnect the graph). Note that I've left some of the minor details (basic counting, algebraic manipulations, etc.) to you; please take the time to verify them for yourself, and ask if you think anything is unclear. Hope this helps.
$\endgroup$ 1
