# Edge connectivity of a graph with diameter 2

If G is a graph of diameter 2, then $\kappa_1(G) = \delta(G)$ where $\kappa_1(G)$ is the edge connectivity of $G$. The Chartrand/Lesniak proof goes as follows: Let $S$ be an edge cut with $|S|=\kappa_1(G)$, and let $H_1, H_2$ be the component graphs of $G-S$ with $|H_1| <= |H_2|$. Since $G$ has diameter 2, every vertex of $H_2$ is adjacent to some vertex of $H_1$. How?

I choose a vertex $u$ from $H_2$; if it's not adjacent to some vertex $v$ in $H_1$ then the graph diameter tells me there exists a vertex $w$ in $H_2$ mutually adjacent to both. So I see how half the vertices of $H_2$ are adjacent to vertices of $H_1$...

• Yes it does sound weird. If I take a star graph and remove a single edge, $H1$ has 1 vertex, and only one vertex of $H_2$ has neighbors in $H_1$. Can you tell us where we can find the proof? – Manuel Lafond Nov 19 '16 at 5:27
• By that example, the $w$ of my second paragraph could be shared by all other vertices of $H_2$ invalidating my last statement. The theorem is actually credited to Plesnik (1975), an outline of which can be found on page 5 of this document. Perhaps I'm misreading it. – bvy Nov 19 '16 at 15:42
• The outline I linked to leaves out some steps. There's a presupposition that $H_1$ contains a vertex not incident any vertex of $H_2$, in which case all the vertices of $H_2$ are incident with vertices in $H_1$. This comes from the proof in the 4th edition of Graphs & Digraphs by Chartrand and Lesniak. Even then it's not very clear. The proof in the 6th edition is much clearer. I'm posting an answer to my own question. – bvy Nov 20 '16 at 15:46

Suppose there are vertices $r$ in $H_1$ and $s$ in $H_2$ such that neither vertex is incident an edge of $|S|$. Then $d(r,s) >= 3$ which is a contradiction. So (without loss of generality?) if there is a vertex of $H_1$ not incident any vertex of $H_2$, it must be true that every vertex of $H_2$ is incident some vertex of $H_1$.