Probabilistic r-way cut set algorithm
Your idea of stopping when there are $r$ vertices remaining is the correct approach. Now let us see how to bound the success probability of contracting one arbitrary edge not in a fixed $r$ way cut-sets.

Denote the graph by $(V,E)$ with $n=|V|$ and $m=|E|$.

Lemma: Let $C$ be an $r$-way minimum cut. The probability that a randomly selected edge is not in $C$ is at least 
$$\frac{(n-r+1)(n-r)}{n(n-1)}.$$

Proof:
Let us count the number of elements in the following sets.

$$\begin{align}
V^{r-1}&amp;=\{Q: Q \subseteq V\text{ such that } |Q| = r-1\}\\
S&amp;=\{(e, Q):  Q\in V^{r-1}, e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
S_{e}&amp;=\{\phantom{(e,\,} Q\phantom{)}: Q\in V^{r-1}\phantom{, e\in E } \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
S_{Q}&amp;=\{\phantom{(}e\phantom{,Q)}: \phantom{Q\in V^{r-1},\,} e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
\end{align}$$

$|V^{r-1}|=\binom{n}{r-1}.$
$|S_e|=\binom{n-2}{r-1}$ for all $e\in V$.

Fix an arbitrary $Q\in V^{r-1}$. If we removes all edges not in $S_Q$, i.e., all edges whose endpoints are in $Q$ and all edges between a vertex in $Q$ and a vertex not in $Q$, there will be $r-1$ connected components of single vertex and one or more connected components in the remaining vertices. That means the set of all edges not in $S_Q$ is an $r$-way cut. Since the minimize size of an $r$-way cut is $k$, the number of edges not in $S_Q$ is no less than $k$, i.e, $|S_Q|\le m-k.$

Since $S$ is the disjoint union of all $S_e$, $e\in E$ as well as the disjoint union of all $S_Q$, $Q\in V^{r-1}$,
$$\binom{n-2}{r-1}m \le (m-k)\binom n{r-1},$$
which means,
$$1-\frac k{m} \ge\frac{\binom{n-2}{r-1}}{\binom n{r-1}}=\frac{(n-r+1)(n-r)}{n(n-1)},$$
where the left side is exactly the probability that a randomly selected edge from $E$ is not in $C$, a set of $k$ edges. QED.





Now that we have the lemma above, we can proceed just as in the book to compute the probability that any given minimum $r$-way cut $C$ survives all $n − r$ random successive edge contractions.





Exercise. (One minute or less) Check that the lemma and its proof above  specialize to the arguments given in the book in the case of $r=2$.