[Graph Theory problem solving] Deduce that $e(T_{n,k}) = \left \lfloor \left(\frac{k-1}{2k} \right) n^2\right \rfloor$ for all $k < 8$

I will solve a graph theory problem:

Deduce that $e(T_{n,k}) = \left \lfloor \left(\frac{k-1}{2k} \right) n^2\right \rfloor$ for all $k < 8$

I recommend that you read this post, first.

Graph Theory Problem Solving:

Since $k<8$, $-\frac{k}{8} > -1$. Therefore, $\frac{n^2(k-1)}{2k} – \frac{k}{8} >\frac{n^2(k-1)}{2k} -1$ and $ \left \lceil \frac{n^2(k-1)}{2k} – \frac{k}{8}\right \rceil  \geq \left \lfloor \frac{n^2(k-1)}{2k} \right \rfloor$. Since $e(T_{n,k})$ is an integer, $ \left \lfloor \frac{n^2(k-1)}{2k} \right \rfloor \leq \left \lceil \frac{n^2(k-1)}{2k} – \frac{k}{8}\right \rceil \leq e(T_{n,k}) \leq \left \lfloor \frac{n^2(k-1)}{2k} \right \rfloor$. Therefore, $$e(T_{n,k}) = \left \lfloor \frac{n^2(k-1)}{2k} \right \rfloor$$.


Related Posts:

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

[그래프이론 (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

Leave a Comment