Show that if $\kappa(G) \leq 1$ then $\lambda(G) \leq \frac{\Delta(G)}{2}$

227 Views Asked by At

The exercise is givien as the title says, I can't see no point using that $\kappa(G) \leq \lambda(G) \leq \delta(G) \leq \Delta(G)$, but is the only inequality that I know related with the connectivity with edges or vertex.

Little addition, it is obvious that only exists two cases, $\kappa(G) = 0$ which makes the Graph void. And $\kappa(G) = 1$ so the Graph has a cut point, anyway, I can't see any further or a relation with $\lambda(G)$ besides the inequality.

Any hints?

1

There are 1 best solutions below

1
On

Is it right that $\lambda$ is the minimum size of edge cut?

Then, the problem is easy. (Cosider only for $\kappa=1$).

Choose such cut vertex $v$. Let $C_1,\cdots,C_k$ be the components of $G-v$. And observe edges incident with $v$ and $C_i$.

From the fact that $k\geq 2$, we can find some $C_i$ which has at most $\Delta/2$ edges between $v$. These edges make $\lambda \leq\Delta/2$.