What is the intuition behind this question (Graph theory with applications, Bondy and Murty Q1.2.9)

Question

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!

Answer 1

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$$

Answer 2

Here is more “talky” way to present bof’s answer.

Within each partite part (of vertices), number (label) the vertices from $1$ to $k$ (or $k+1$). Choose one of the partite parts with $k$ vertices and call it $L$ (for “leftmost.”) The edges of $T_{m,n}$ are in exactly one of the following three sets:

$E$: the set of edges not involving a vertex of $L$.

$U$ (for “up”): the set of edges from a vertex $v_i$ in $L$ to a vertex with label less than or equal to $i$. (“Up” is really “up or straight across.”)

$D$ (for “down”): the set of edges from a vertex $v_i$ in $L$ to a vertex with label greater than $i$.

The number of edges in $T_{m,n}$ is $|E|+|U|+|D|$.

The number of edges in $U$ is easiest to count. There are $k$ choices for the vertex in $L$, and if the vertex in $L$ is $v_i$, there are $(m-1)i$ choices for the other vertex, since it can be in any one of the $m-1$ other partite parts and must have label less than or equal to $i$. So there are $(m-1)\sum_{i=1}^{k} i=\color{red}{(m-1){k+1\choose2}}$ edges in $U$.

Now consider the edges in $D$. Each of them connects a vertex $v_i$ of $L$ to a higher-numbered vertex elsewhere. “Reposition” the $v_i$ end of each of these out of $L$ and to the vertex labeled $i$ in the same partite set as the end of the edge not in $L$ (that is, into the partite part at the “right-hand” end of the edge). There is always such a vertex, because each partite set has at least as many vertices as $L$, and the result connects distinct vertices because the labels at the vertices of an edge in $D$ are never the same; $D$ means “strictly down.” Call the resulting set of edges $D'$. The repositioning of edges is one-to-one, so $|D'|=|D|$.

It should be easy to see that $D'$ is disjoint from $E$ and that $D'\cup E$ is the set of edges for the complete graph on the set of vertices of $T_{m,n}\setminus L$. Then there are $\color\red{{n-k}\choose2}$ edges in $D'\cup E$, hence in $D$ and $E$ together.