Find the minimum positive integer $r$ for which there exists an $r$-regular graph $G$ such that $\kappa(G) \neq \lambda(G)$

320 Views Asked by At

Find the minimum positive integer $r$ for which there exists an $r$-regular graph $G$ such that $\kappa(G) \neq \lambda(G)$. Verify your answer.

(Chartrand, Gary, and Ping Zhang. A First Course in Graph Theory. Mineola, NY: Dover Publications, 2012.)

I know from a theorem that $\kappa(G) \leq \lambda(G)$ for every graph $G$.

Here is my attempt: Let $L$ be a minimum-edge-cut for $G$. Then $G-L$ has exactly two components $C_1,C_2$ - only two for otherwise one can find a smaller cut.

Assume now that no two edges in $L$ share an end-vertex (otherwise $\kappa < \lambda$).

$|L|=\lambda(G)$

Furthermore, since $G$ is regular and no two edges in $L$ are incident to a same vertex, both $|C_1|,|C_2| \geq r-1$

$\implies |G|\geq 2(r-1) \implies r \leq 1+\frac{|G|}{2}$. So the opposite of this condition would imply the assumption is not true i.e. $r > 1+\frac{|G|}{2}$. In addition, $r\leq |G|-1$.

Plotting these two inequalities gives $r\geq 4$ for the question.

Is my working correct?