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.


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). $$

  • 1
    $\begingroup$ That was awesome !!! thank you !!! really thank you !!! $\endgroup$ – Arman Malekzadeh Mar 3 '16 at 13:09

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.