The Turan graph $T_{n,r}$ is the compelete $r$-partite graph with $b$ partite sets of size $a+1$ and $r - b$ partite sets of size $a$, where $a = \lfloor n/r \rfloor$ and $b = n - ra$.

 

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7

---

Solution

1. Prove that $e(T_{n,r}) = (1 - \frac{1}{r})\frac{n^2}{2} - \frac{b(r-b)}{2r}$.

a. The degree of a vertex $v$ in an independent set of size $a$ is $\deg_G(v) = n - a$.
- The degree of a vertex $v$ in an independent set of size $a+1$ is $\deg_G(v) = n - a - 1$.

b. For independent sets of size $a$, there are $r-b$ such sets, each containing $a$ vertices.
- The total degree of these vertices is $(r-b)a(n-a)$.
- For independent sets of size $a+1$, there are $b$ such sets, each containing $a+1$ vertices.
- The total degree of these vertices is $b(a+1)(n-a-1)$.

c. Thus,
$$\sum_{v \in V(G)} \deg_G(v) = (r-b)a(n-a) + b(a+1)(n-a-1)$$
$$= (n-a)(ra+b) - b(a+1).$$

d. Since $b = n - ra$, it follows that $ra + b = n$. Thus,
$$\sum_{v \in V(G)} \deg_G(v) = (n-a)n - b(a+1).$$

e. Since $b = n - ra$ and $a = \frac{n}{r} - \frac{b}{r}$,
$$\sum_{v \in V(G)} \deg_G(v) = \left(n - \frac{n}{r} + \frac{b}{r}\right)n - b\left(\frac{n}{r} - \frac{b}{r} + 1\right).$$
Simplify:
$$= n^2\left(1 - \frac{1}{r}\right) + \left(\frac{b^2}{r} - b\right) = 2e(G).$$

f. Therefore,
$$e(G) = e(T_{n,r}) = \left(1 - \frac{1}{r}\right)\frac{n^2}{2} - \frac{b(r-b)}{2r}.$$

2. Determine when strict inequality occurs.

a. Since $e(G)$ must be an integer, check when fractional values occur:
- For the first term, if $\frac{n^2}{2}$ is not an integer or $\frac{n^2}{2} \cdot \frac{1}{r}$ is not an integer, then $e(G)$ is not an integer.
- For the second term, since $b = n - ra$, if $b \neq 0$ and $r$ does not divide $n$, this term introduces a fractional value, making $e(G)$ non-integer.

b. Strict inequality occurs when $b \neq 0$ (i.e., $r$ does not divide $n$).
- The second term introduces a fractional part, forcing $e(T_{n,r})$ to be strictly less than the rounded value.

c. Therefore:
- If $r$ divides $n$, then $b = 0$, and
$$e(T_{n,r}) = \left(1 - \frac{1}{r}\right)\frac{n^2}{2}.$$
- If $r$ does not divide $n$, then $b \neq 0$, and strict inequality occurs:
$$e(T_{n,r}) < \lfloor(1 - \frac{1}{r})\frac{n^2}{2}\rfloor.$$