[Graph Theory problem solving] Show that $(\frac{k-1}{2k})n^2 – \frac{1}{8 k} \leq e (T_{n,k}) \leq (\frac{k-1}{2k}) n^2$.

I will solve a graph theory problem:

Show that $(\frac{k-1}{2k})n^2 – \frac{1}{8 k} \leq e (T_{n,k}) \leq (\frac{k-1}{2k}) n^2$.

Graph Theory Problem Solving:

There exists $b \in \{0,1,2,…,k-1\}$ such that $n = k \lfloor \frac{n}{k} \rfloor +b $.
Let $A = \{ v \in V(T_{n,k}) \mid \text{ $v$ is in an independent set whose size is } \lfloor \frac{n}{k} \rfloor \}$ and $B = V(T_{n,k})-A$.

$$\begin{align*} 2e(T_{n,k}) &= \sum_{v \in V(T_{n,k})} deg_{T_{n,k}} (v) \\ &= \sum_{v \in A} deg_{T_{n,k}} (v)+\sum_{v \in B} deg_{T_{n,k}} (v) \\ &= \sum_{v \in A} \left( n – \left\lfloor \frac{n}{k} \right\rfloor\right) +\sum_{v \in B} \left( n – \left\lfloor \frac{n}{k} \right\rfloor-1\right)\\ &= \sum_{v \in V(T_{n,k})} \left( n – \left\lfloor \frac{n}{k} \right\rfloor\right) – |B| \\ &= n\left( n – \left\lfloor \frac{n}{k} \right\rfloor\right) –   b \left( 1+ \left \lfloor \frac{n}{k} \right \rfloor  \right)\end{align*} $$

Putting $\left \lfloor \frac{n}{k} \right \rfloor = \frac{n}{k}- \frac{b}{k},$ $$ e(T_{n,k}) = \frac{n^2 (k-1)}{2k} – \frac{b(k-b)}{2k}$$.

Let $f(x) = – \frac{x(k-x)}{2k}$. $f(x)$ has a minimum at $x=\frac{k}{2}$ and $f(\frac{k}{2})=-\frac{k}{8}$. Therefore,

$$ \frac{n^2(k-1)}{2k} – \frac{k}{8} \leq e (T_{n,k}) \leq \frac{ n^2(k-1)}{2k}$$

Related Posts:

[그래프이론 (Graph Theory) 문제풀이] 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. (a) Prove that e(T_{n,r}) =\left( 1- \frac{1}{r} \right)\frac{n^2}{2} - \frac{b(r-b)}{2r} . (b) Since e(G) must be an integer, part (a) imples e(T_{n,r}) ≤ \lfloor (1-\frac{1}{r}) \frac{n^2}{2} \rfloor Determine when strict inequality occurs

Source: Homework problem from Professor Choi‘s Graph Theory class, Gwangju Institute of Science and Technology, Fall Semester 2023