0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Manuel Lafond Nov 19 '16 at 5:27
  • $\begingroup$ 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. $\endgroup$ – bvy Nov 19 '16 at 15:42
  • $\begingroup$ 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. $\endgroup$ – bvy Nov 20 '16 at 15:46
0
$\begingroup$

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

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