Show that if $G$ is a noncomplete graph of order $n$, then $t(G)≤\frac {n-α(G)}{α(G)}$

97 Views Asked by At

Show that if $G$ is a non-complete graph of order $n$, then $t(G)≤\frac {n-α(G)}{α(G)}$

with $\kappa(G)$ is connectivity of $G$, $\alpha (G)$ is the independent vertices of $G$, and $t(G)$ is the toughness of $G$

I know that for every non-complete graph $G$

$$\frac{\kappa (G)}{\alpha(G)} \leq t(G) \leq \frac{\kappa(G)}{2}$$

I'm not sure I can see the relationship between $n$ and $\kappa (G)$ and $\alpha (G)$ that give me that result.

1

There are 1 best solutions below

2
On BEST ANSWER

By removing all vertices except an independant set of size $\alpha(G)$, it is possible to split $G$ into $\alpha(G)$ components. Since $G$ is $t(G)$-tough, we must have removed at least $t(G)\alpha(G)$ vertices. We conclude $$t(G)\alpha(G)\le n-\alpha(G)$$