Before revision:  This also gives an extremal bound of O_k(n^k) on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime.
After revision:  This also gives an extremal bound of O_k(n^k) on the number of minimum k-cuts and an algorithm to compute a minimum k-cut in similar runtime.