Prove that $\lambda (G) \leq r/2$ if $\kappa(G) = 1$ of r-regular connected graph $G$ and $r > 1$

138 Views Asked by At

This is a question I found on exercise book. But I dont think it is true.

For example, this graph:

enter image description here

It is an upsided triangle on the top, and a triangle at the bottom. In this case, $\lambda(G) > r/2$.

2

There are 2 best solutions below

1
On

That graph isn't regular. The middle vertex has $4$ neighbors, but the other vertices have $2$.

0
On

Same idea, if $κ(G)=1$ it has a cut vertex, now use Menger's theorem which states that you will have $λ(G)$ edgedisjoint paths between two nodes of the graph, now if our nodes are on either side of the cutvertex then the maximum amount of such paths is clearly $\frac r2$