1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What are Kappa, Lambda and Delta? $\endgroup$ – Tom Smith May 15 '10 at 12:27
  • 1
    $\begingroup$ Sorry - I actually thought about putting the definitions in but forgot! Kappa is the smallest k for which G has a k-cut. Lambda is the smallest k for which G has a k-edge cut. Delta is the smallest degree in G. $\endgroup$ – lardydah May 15 '10 at 12:28
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Or, similarly but maybe a little more simply: let {u,v} be a two-vertex cut, and let x and y be vertices on opposite sides of the cut. If G were 5-edge-connected then there would be five edge-disjoint paths from x to y, each of which passes through u or v (or both); therefore, by the pigeonhole principle, at least three of the paths would have to go through one of the two vertices u and v, an impossibility. $\endgroup$ – David Eppstein May 15 '10 at 21:20

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.