Any graph $(V,E)$ with $m$ edges and more than $k$ vertices has a $k$-cut of value at least $(k-1)m/k.$ ###### Proof: Consider the random process where we place each vertex into one of $k$ sets independently with probability $\frac{1}{k}$ each. Then the sample space $\Omega$ is the set of $k$-cuts of the graph. Let $m=|E|$ and $e_{1},e_{2},\dots,e_{m}$ be an enumeration of the edges of the graph. For $i=1,2,\dots,m$ define $X_{i}:\Omega\to \mathbb{R}$ by $X_{i}(\omega)=\begin{cases} 1 & e_{i}\text{ is in the cut }\omega \\ 0 &\text{otherwise} \end{cases}$Then for all cuts $\omega\in \Omega,$ the value of the cut is given by $X(\omega)=\sum_{i=1}^{m}X_{i}(\omega).$ Then by linearity of expectation, $\mathbb{E}[X]=\sum_{i=1}^{m} \mathbb{E}[X_{i}] = \sum_{i=1}^{m} \mathbb{P}(X_{i}=1)= m(k-1)/k$since $\mathbb{P}(X_{i}=1)$ is the probability that the endpoints of $e_{i}$ are placed in two different sets which equals ${k \choose 2}\times \frac{1}{k^{2}}=(k-1)/k.$ Finally, by [[Probabilistic Method]], we conclude that there exists a $k$-cut of value at least $(k-1)m/k.$