Graph Theory inequality

Question

I've been trying to prove the following inequality

If G is r-regular graph and $\kappa (G)=1 $, then $\lambda (G)\leq \left \lfloor \frac{r}{2} \right \rfloor$

I've tried manipulating the Whitney inequality, but it doesn't seem to help.

Answer 1

Let $G=(V,E)$ be the $r$-regular graph. Since $\kappa(G)=1$, there exist three vertices $u$, $v$ and $x$ such that, after removing $x$ from $G$, $u$ and $v$ are not connected. Call $G'$ the graph obtained by removing $x$ from $G$, and define

$$ G_u=\{ y \in V \;|\; y \mbox{ is connected to } u \mbox{ in } G' \}$$ $$ G_v=\{ y \in V \;|\; y \mbox{ is connected to } v \mbox{ in } G' \}.$$

$G_u$ and $G_v$ are not connected in $G'$. Now define

$$ E_u=\{(x,y) \in E | y \in G_u \} $$ $$ E_v=\{(x,y) \in E | y \in G_v \}. $$ Observe that by removing one of these two sets the graph obtained is disconnected. Moreover,

$$ |E_u|+|E_v|=d(x)=r.$$ Hence one of them has cardinality $\leq \lfloor\frac{r}{2} \rfloor$.