Proving edge connectivity

Question

Let $G$ be a $5$-regular graph with $\kappa(G) = 2$. Prove that $\lambda(G) \leq 4$.

As part of my revision for a graph theory I'm doing through some provided questions and answers, however the answer to the above wasn't provided.

I know that a $5$-regular graph contains vertices all with degree $5$.

So using Whitney's theorem we have: $\kappa(G) = 2 \leq \lambda(G) \leq 4 \leq \Delta(G) = 5$.

I'm just not really sure how to approach proving that Lambda is less than $5$.

If every vertex $v$ has degree $5$ and $\kappa(G) = 2$ then there must be $2$ internally disjoint paths between any $u$ and $v$ in the graph.

because of these two internally disjoint paths, the edges of $u$ must be split between these two paths, as such one path would have $2$ edges and another $3$ edges. This would be the same as $v$, which would at most have $2$ edges from one path and $3$ from the other.

This means that to destroy the connectivity of the graph, you could cut the two edges from $u$ and the two edges to $v$. If one or both of the paths have only $1$ edge, then the number of edges to cut will always be $\leq 4$.

Is this a sufficent proof? Is there anyway of making it simpler/neater?

Thanks

Answer 1

I don't think your argument quite works. In particular, you can't really conclude anything about the lengths of your paths. Here's a sketch of a proof using Menger's Theorem. By way of contradiction, assume that the edge-connectivity of $G$ is 5. Let $u, v \in V(G)$. By the edge-version of Menger's theorem, there are 5 edge-disjoint paths between $u$ and $v$. Since, $G$ is 5-regular, no three of these paths can intersect at a common vertex (other than $u$ or $v$). It is thus easy to construct 3 vertex-disjoint paths between $u$ and $v$. By the vertex-version of Menger's theorem, $G$ is 3-connected, which is a contradiction.