a) Determine the toughness of the compete $k$-partite graph $ K_{n_1,n_2,…,n_k }$ where $n_1≤n_2≤⋯≤n_k$
b) Show that for every non-negative rational number $r$, there exist a graph $G$ with $t(G)=r$
a)
Let $G_1,G_2,…,G_k$ be the partites of $G$ with order $n_1,n_2,…,n_k$ respectively. Since $n_1≤n_2≤⋯≤n_k$, $U_1$ is the smallest partite. By the definition of $K_{n_1,n_2,…,n_k }$, $K_{n_1,n_2,…,n_k }$ has order $n=n_1+n_2+⋯+n_k$. Let $S$ be the vertex cut of $G, then
$$|S|≥n_1+n_2+⋯+n_(k-1)=n-n_k$$
and
$$g(G-S)=n_k$$
So by the definition of toughness
$$t(G)=\frac{|S|}{g(G-S)} = \frac{n-n_k}{n_k}$$
b)
Let $r$ be a non-negative rational number, then there exists positive integers $a$ and $b$ such that $r= \frac{a}{b}$
The book told me to apply part a), but I can't see how I can do it. Part a) is true for $K$-partitie graph, but I don't know if it's true for every graph.
It need not be true for every graph. You are asked to show that there exists some graph $G$ with $t(G)=r=\frac ab$. If it makes life easy, you migh pick a $k$-partite graph. In other words, try to find a $k$-partite graph with $k_n=b$ and $n=a+b$. Since $n_k$ must be the largest partite, you may have choose $k$ and all $n_i$ wisely.