This is question 1.2.9 from Graph theory with applications by Bondy and Murty that I am working through for fun (this book is freely available online, and I highly recommend it).
Question, I am working on part (a).
We are asked to show that $T_{m,n}$, the complete $m$-partite graph on $n$ vertices where each part has $[n/m]$ or $\{n/m\}$ vertices satisfies
$$\varepsilon(T_{m,n}) = {n-k \choose 2} + (m-1){k+1 \choose 2} ,$$
where $\varepsilon(G)$ counts the number of edges of $G$ and $k = [n/m]$.
My approach is as follows. For a general complete $m$-partite graph $G$ with $n$ vertices having parts $V_1, \ldots, V_m$, we have that each vertex $v$ in part $i$ has $\deg{v} = n – |V_i|$, and there are $|V_i|$ such vertices in $V_i$. Then
$$\varepsilon (G) = \sum\limits_{v\in G} \frac{\deg(v)}{2} = \sum\limits_{i=1}^m |V_i| \frac{n-|V_i|}{2} =\frac{n^2}{2} – \sum\limits_{i=1}^m \frac{|V_i|^2}{2}. $$
So far so good I think.
Now, if we let $n = mk + d$ where $d \in[0,m)$, and set $|V_i| = k+1$ for $i = 1,\ldots, d$ and $|V_i| = k $ for $i = d+1,\ldots, m$, we obtain $T_{m,n}$. Then we have
$$\varepsilon(T_{m,n}) = \frac{n^2}{2} – \sum\limits_{i=1}^d\frac{(k+1)^2}{2} – \sum\limits_{i=d+1}^m \frac{k^2}{2}= \frac{n^2}{2} -\frac{mk^2}{2} – d\frac{2k+1}{2}. $$
I have tried doing algebra to this expression and also the required outcome but I cannot seem to show their equality. So my question now is as follows:
Is my working so far indeed correct, and if so, is there an easy way to show the equality of two expressions. Further more, the required outcome looks like a simple combinatorial counting argument that should be intuitively clear, but I do not see it, can anyone explain? Thanks a lot!
Best Answer
First, for the benefit of those who don't have a copy of Bondy & Murty, let me explain that the notations $[x]$ and $\{x\}$ denote the integer floor and ceiling of $x,$ nowadays usually written as $\lfloor x\rfloor$ and $\lceil x\rceil.$
Let $V_0,V_1,\dots,V_{m-1}$ be the parts of the $m$-partite graph $T=T_{m,n}.$ Each part has either $k$ or $k+1$ vertices; since at least one part has exactly $k$ vertices, we may assume that $|V_0|=k.$
Define a function $f:V\to\{1,2,\dots,k+1\}$ so that, for each $i\in\{0,1,\dots,m-1\},$ the restriction of $f$ to $V_i$ is a bijection from $V_i$ to $\{1,2,\dots,|V_i|\}.$
For $1\le i\le m-1,$ the number of edges $xy\in E(T)$ with $x\in V_0$, $y\in V_i,$ and $f(y)\le f(x)$ is equal to $\binom{k+1}2,$ the number of integer pairs $(r,s)$ with $1\le s\le r\le k.$ Therefore, if we define $E_0=\{xy\in E(T):x\in V_0,\ f(y)\le f(x)\}$ and $E_1=\{xy\in E(T):x\in V_0,\ f(x)\lt f(y)\},$ then $$|E_0|=(m-1)\binom{k+1}2.\tag1$$
Let $K$ be the complete graph on the vertex set $V\setminus V_0.$ Observe that there is a one-to-one correspondence between $E_1$ and $E(K)\setminus E(T);$ namely, an edge $xy\in E_1$ with $x\in V_0$, $y\in V_i$, and $f(x)\lt f(y)$ corresponds to the edge $zy\in E(K)\setminus E(T)$ where $z\in V_i$ and $f(z)=f(x).$ It follows that $|E(K)\setminus E(T)|=|E_1|$ and so $$|E(T)\setminus E_0|=|E_1|+|E(K)|-|E(K)\setminus E(T)|=|E(K)|=\binom{n-k}2.\tag2$$ Adding $(1)$ and $(2)$ we get $$|E(T)|=\binom{n-k}2+(m-1)\binom{k+1}2.\tag3$$