Graph Theory – Proving Edge Connectivity Equals Minimum Degree in Diameter 2 Graph

connectednessgraph theory

A graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration.
$$\operatorname{diam}(G)=\max\{d(u,v):u,v\in V(G)
\}$$

The edge-connectivity of $G$, $\kappa'(G)$, is the minimum cardinal of the cuts in $G$.
$$\delta(G)=\min\left\{\operatorname{deg}(v):v\in V(G)\right\}.$$
Now i want to prove that for any simple graph with diameter 2, $\kappa'(G)=\delta(G)$.

Note: I know there exists a similiar proof for digraphs but I want to prove this theorem for simple graphs.

Thanks in advance.

Best Answer

The inequality $\kappa'(G)\leqslant \delta(G)$ holds for any connected graph, since the edges incident to a vertex of minimum degree form an edge cut. For the reverse inequality, let let $G=(V,E)$ be a graph with $\operatorname{diam}(G)=2$ and $[S,\overline S]$ be a minimum edge cut with $|S|\leqslant |\overline S|$. Then every vertex in $S$ is adjacent to a vertex in $\overline S$. For if not, there would be a vertex $u\in S$ such that for each $v\in\overline S$, there is a path $u\to w\to v$ in $G$, which implies that $$|[S,\overline S]|\geqslant |\overline S|\geqslant \frac{|V|}2. $$ Then $\deg u\leqslant |S|-1<\frac{|V|}2$, so that $$\delta(G)\leqslant d(u)<\frac{|V|}2\leqslant |[S,\overline S]|=\kappa'(G), $$ a contradiction. Since $|[S,\overline S]|= \sum_{v\in S}\deg v - 2e(G[S])$ , it follows that \begin{align} |[S,\overline S]|&\geqslant |S|\delta(G) - |S|(|S|-1)\\&\geqslant |S|\delta(G)-\delta(G)(|S|-1)\\&=\delta(G), \end{align} and hence $$\delta(G)\leqslant |[S,\overline S]|=\kappa'(G). $$

Related Question