Formula for the number of edges of complete $m$-partite graph The complete $m$-partite graph on $n$ vertex in which each part has either $[n/m]$ ($n/m$ rounded down to an integer) or $\{n/m\}$ ($n/m$ rounded up to an integer) vertices is denoted by $T_{m,n}$. Show that
\begin{equation}
\epsilon(T_{m,n})=\binom{n-k}{2}+(m-1)\binom{k+1}{2},\mathrm{where} \;k=[n/m].
\end{equation}
My efforts:
Use induction. Obviously $\epsilon(T_{2,2})=1$ and the formula is correct. First fix $m$ and vary $n$. Assume the formula holds for $n$. Consider $\epsilon(T_{m,n+1})$. One vertex is added to the partition with [$n/m$] vertices. The new vertex can be connected to any vertex in the other partitions. Thus
\begin{equation} 
\begin{split}
\epsilon(T_{m,n+1}) & = \epsilon(T_{m,n})+n-[n/m] \\
 & = \binom{n-[n/m]}{2}+(m-1)\binom{[n/m]+1}{2}+n-[n/m]
\end{split}
\end{equation}
We need to consider two cases: $[(n+1)/m]=[n/m]$ and $[(n+1)/m]=[n/m]+1$.
(1) $[(n+1)/m]=[n/m]$.
\begin{equation}
\begin{split}
\epsilon(T_{m,n+1}) & = \binom{n-[\frac{n+1}{m}]}{2}+(m-1)\binom{[\frac{n+1}{m}]+1}{2}+\binom{n-[\frac{n+1}{m}]}{1} \\
 & = \binom{n+1-[\frac{n+1}{m}]}{2}+(m-1)\binom{[\frac{n+1}{m}]+1}{2}
\end{split}
\end{equation}
The formula is correct.
(2) $[(n+1)/m]=[n/m]+1$. This happens only if $(n+1)/m$ is an integer.
\begin{equation} 
\begin{split}
\epsilon(T_{m,n+1}) & = \binom{n+1-[\frac{n+1}{m}]}{2}+\frac{1}{2}(m-1)([\frac{n}{m}]+1)[\frac{n}{m}]+n-[\frac{n}{m}] \\
 & = \binom{n+1-[\frac{n+1}{m}]}{2}+\frac{1}{2}(m-1)([\frac{n+1}{m}])[\frac{n}{m}]+n-[\frac{n}{m}] \\
 & = \binom{n+1-[\frac{n+1}{m}]}{2}+\frac{m-1}{2}([\frac{n+1}{m}])[\frac{n}{m}]+m[\frac{n+1}{m}]-[\frac{n+1}{m}] \\
 & = \binom{n+1-[\frac{n+1}{m}]}{2}+\frac{m-1}{2}([\frac{n+1}{m}])[\frac{n}{m}]+(m-1)[\frac{n+1}{m}] \\
 & = \binom{n+1-[\frac{n+1}{m}]}{2}+\frac{m-1}{2}[\frac{n+1}{m}]([\frac{n}{m}]+2) \\
 & = \binom{n+1-[\frac{n+1}{m}]}{2}+\frac{m-1}{2}[\frac{n+1}{m}]([\frac{n+1}{m}]+1) \\
 & = \binom{n+1-[\frac{n+1}{m}]}{2}+\binom{[\frac{n+1}{m}]+1}{2}
\end{split}
\end{equation}
The formula is again correct.
Then I don't know how to do induction of fixing $n$ and varying $m$. Is there any elegant counting method without using induction?
 A: The idea of this proof is that we can count pairs of vertices in our graph of a certain form. Some of them will be edges, but some of them won't be. When we get a pair that isn't an edge, we will give a bijective map from these "bad" pairs to pairs of vertices that correspond to edges.
Label the parts $X_1, X_2, \ldots, X_m$, and label the vertices in $X_i$ by $x_{i,1}, x_{i,2},\ldots, x_{i,j}$ where either $j=k$ or $j=k+1$. Without loss of generality, assume that $|X_1|=k$, since there must be at least one part of size $k$. The term ${n-k\choose 2}$ counts the number of ways to pick pairs of vertices $\{x_{i,j}, x_{k,l}\}$ from $X_2, X_3, \ldots, X_m$. If $i\neq k$, then $\{x_{i,j}, x_{k,l}\}$ is an edge in the graph. Otherwise, we have $i=k$. We give a map from such pairs of vertices to edges in the graph. Without loss of generality, assume $j<l$. We map the pair $\{x_{i,j}, x_{i,l}\}$ to the pair $\{x_{1,j}, x_{i,l}\}$, which is an edge in our graph. This counts every edge between two vertices not from $X_1$, and every edge of the form $\{x_{1,j}, x_{i,l}\}$ where $i>1$ and $j<l$.
It remains to count the vertices of the form $\{x_{1,j}, x_{i,l}\}$ where $i>1$ and $j\geq l$. First, choose one of the $m-1$ parts other than $X_1$. Let this part be $X_i$. Add a vertex denoted $x_{1,k+1}$ to $X_1$. There are ${k+1\choose 2}$ ways to choose a pair of vertices $\{x_{1,j}, x_{1,l}\}$ from $X_1\cup\{x_{1,k+1}\}$. Without loss of generality, assume $j<l$. If $l<k+1$, then map this pair of vertices to the pair $\{x_{i,j}, x_{1,l}\}$, which is an edge in the graph. Otherwise, if $l=k+1$, we map this pair of vertices to the pair $\{x_{i,j}, x_{1,j}\}$. Hence, we've counted the rest of the edges of the desired form, and these edges are counted by $m{k+1\choose 2}$, completing the proof.
A: You don't need to separately induct on $m$.  Instead, you can just use a separate base case for each $m$, and then use the induction you have done on $n$ to cover every possible value of $n$.  Assuming you require $n\geq m$, this just means you have to check the case of $T_{m,m}$ for each $m$.  (There's not really any reason to require $n\geq m$, though; there's nothing wrong with parts being empty.  So, really the base case is $T_{m,0}$ for each $m$, which is quite easy to check since you just get $0$ edges.)
That said, you can also just count directly without induction.  Kevin Long's answer shows a clever way to do this to make the answer pop out, but you can also count without any cleverness and then just bash out algebra.   Let $n=km+r$, so we have $r$ parts of size $k+1$ and $m-r$ parts of size $k$.  Each vertex in a part of size $k+1$ is connected to $n-(k+1)$ other vertices, so this gives $r(k+1)(n-(k+1))$ edges.  Each vertex in a part of size $k$ is connected to $n-k$ other verices, giving $(m-r)k(n-k)$ edges.  But this counts each edge twice (once for each vertex), so we have a total of $$\frac{r(k+1)(n-(k+1))+(m-r)k(n-k)}{2}$$ edges in total.  Now it's just a matter of substituting $r=n-km$ and doing a bunch of algebra to verify this is equal to $\binom{n-k}{2}+(m-1)\binom{k+1}{2}$.
