0
$\begingroup$

Let $G$ be a simple connected graph with $diam(G)=2$ and $S\subset E(G)$ with l(G) edges where $l(G)$ is the edge connectivity of the graph such that $G-S$ is not connected. I want to show that at least one of the connected parts of $G-S$ is isomorphic to $K_1$ or to $K_a$ where a is the minimum degree of the vertices of the graph G.

$\endgroup$
0
$\begingroup$

Let $k$ be the edge-connectivity of $G$, so $|S|=k$, and $\delta(G)\geq k$. $S$ is a minimal disconnecting set of edges, so $G-S$ has exactly two components(!), call them $X$ and $Y$. Let $A$ be the vertices of $X$ that are endpoints of an edge of $S$. Let $B$ be the vertices of $Y$ that are endpoints of an edge of $S$. We claim that $X-A$ and $Y-B$ cannot both be nonempty: this would exhibit vertices at distance 3(!).

So we may assume that $X=A$. Let $|X|=s$, then $s\leq k$. The degreesum (in $G$) of the vertices of $S$ is at least $ks$. Exactly $k$ edges are leaving $S$, so the degreesum in $S$ is at least $k(s-1)$.

On the other hand the degreesum in $S$ can be at most $s(s-1)$(!). So we either have $s=1$ (in which case $X=K_1$) or $s=k$ (in which case $X=K_k$ and $\delta(G)=k$(!)).

Depending on your knowledge you may want to add a bit more evidence to the places marked with (!).

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