I'm working through Bondy and Murty, the old version which is available online. In exercise 1.2.9a they want to prove the following equality
$$\epsilon(T_{m,n})=\binom{n-k}{2}+(m-1)\binom{k+1}{2}\tag{1}$$
where $ k = [\frac{n}{m}]$ the biggest integer $\le \frac{n}{k}$ and $T_{m,n}$ denoting the Turan graph with $n$ vertices and being a complete and simple $m$-partite graph.
I think I solved the problem, at least I derived an expression for
$$\epsilon(T_{m,n})=k^2\frac{(m-p)(m-p-1)}{2}+k(k+1)(m-p)p+(k+1)^2\frac{p(p-1)}{2}\tag{2}$$
which gives the same results as in the solution provided by Brian M. Scott in this MSE question.
I derived $(2)$ as follows: Write $n=mk+p$, then there are $p$ groups of $k+1$ vertices and $m-p$ groups of $k$ vertices. Thus,
- $k^2\frac{(m-p)(m-p-1)}{2}$, $k^2$ edges between two groups of size $p$ and there are $\frac{(m-p)(m-p-1)}{2}$ of this $k^2$ connection for the $m-p$ groups.
- $k(k+1)(m-p)p$, $k(k+1)$ edges between one group of size $k$ and a group of size $k+1$ and there are $(m-p)p$ of these group connections
- $(k+1)^2\frac{p(p-1)}{2}$, same as point one, just within the $p$ groups each of size $k+1$.
Assuming my derivation is correct, by manipulating $(2)$ we can derive the expression $(1)$. However, I would like to know the motivation of $(1)$ as it seems they solved the problem differently, i.e. two questions:
- Is my expression $(2)$ correct
- What is the interpretation / motivation of $(1)$ as it is in a very specific forumla.
Best Answer
I spent a long month typing up all of the B&M problems I could solve in LaTex. here's my solution for this problem, which I think will illustrate how the formula was conceived. I'll take a look at your answer shortly and try to work it out, but I wanted to kick off with the part of the problem I could solve quickly.
First, note that if $m=1$ then $k=n$ and the formula predicts $\left({0\atop 2}\right)=0$ edges as desired. For the remainder of the problem, we will assume $m>1$. We will create $T_{m,n}$ in a slightly peculiar way and call it combinatorics. Start with an empty graph with $n$ vertices and partition them as evenly as possible into $m$ parts so that some are "small" parts with $k=\left\lfloor \frac{n}{m}\right\rfloor $ vertices and perhaps (but not necessarily) others are "large" parts with $k+1$ vertices. There is at least one small part, so choose one and call it "special".
The first step is to create a complete graph on the $n-k$ vertices that aren't in the special part, and this takes $\left({n-k\atop 2}\right)$ edges (by Problem 1.2.7). Now, let one of the $m-1$ non-special parts be given. We need to remove all of the edges connecting two vertices in this part, and then add all of the edges from every vertex in that part to every vertex in the special part. This is a net increase of $x=ak-\left({a\atop 2}\right)$ edges where a is the number of vertices in the part. If the part is small, then $a=k$ and
$$x=k^{2}-\left({k\atop 2}\right)=\frac{2k^{2}}{2}-\frac{k(k-1)}{2}=\frac{k(k+1)}{2}=\left({k+1\atop 2}\right) $$
and if the part is large then $a=k+1$ and
$$x=k(k+1)-\left({k+1\atop 2}\right)=\frac{2k(k+1)}{2}-\frac{k(k+1)}{2}=\frac{k(k+1)}{2}=\left({k+1\atop 2}\right)$$
So, we are adding $\left({k+1\atop 2}\right)$ edges in either case. Repeating this for the remainder of the $m-1$ non-special parts, we come up with a total of $\left({n-k\atop 2}\right)+(m-1)\left({k+1\atop 2}\right)$ edges. But every vertex is now joined to every vertex except the ones in its part (whether that vertex was a part of the special part or another one), so we have created $T_{m,n}$ as desired.