[그래프이론 (Graph Theory) 문제풀이] The Turan graph [latex]T_{n,r}[/latex] is the compelete r-partite graph with b partite sets of size a+1 and r − b partite sets of size a, where [latex]a = lfloor n/rrfloor [/latex] and b = n − ra. (a) Prove that [latex] e(T_{n,r}) =left( 1- frac{1}{r} right)frac{n^2}{2} - frac{b(r-b)}{2r} [/latex] . (b) Since e(G) must be an integer, part (a) imples [latex] e(T_{n,r}) ≤ lfloor (1-frac{1}{r}) frac{n^2}{2} rfloor[/latex] Determine when strict inequality occurs

그래프이론 (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” 이다.

그래프이론 (Graph Theory) 문제풀이

이번에 풀고자 하는 그래프이론 (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

(풀이)
$deg_G(v) = n-a$ when $v$ belongs to an independent set whose size is $a$ .
$deg_G(v) = (n-a)-1$ when $v$ belongs to an independent set whose size is $a+1$ .
Therefore, $\sum_{v \in V(G)} deg_G(v) = n (n-a) - b(a+1) = 2e(G)$ .
By definition of $a$ and $b$ , $n=ra+b$ where $n=n(G)$ and $0\leq b \leq r-1$ .
Therefore, $a = \frac{n}{r}-\frac{b}{r}$ .
Therefore, $n(n-a)-b(a+1) = n^2 \left( 1- \frac{1}{r}\right)-b \frac{(r-b)}{r}$ .
Therefore, $e(G) = \frac{n^2}{2}\left(1-\frac{1}{r}\right) - \frac{b(r-b)}{2r}$ .
When $r$ divides $n$ , $b=0$ and $e(G) = \frac{n^2}{2} \left(1-\frac{1}{r}\right) = \lfloor \frac{n^2}{2} \left(1-\frac{1}{r}\right) \rfloor$ .
When $r$ does not divides $n$ , $1\leq b \leq r-1$ , $e(G) = \frac{n^2}{2}\left(1-\frac{1}{r}\right) - \frac{b(r-b)}{2r} < \frac{n^2}{2}\left(1-\frac{1}{r}\right)$ .
Therefore, $e(G) \leq \frac{n^2}{2}\left(1-\frac{1}{r}\right) -1 < \lfloor \frac{n^2}{2} \left(1-\frac{1}{r}\right) \rfloor$