Summary my headsolving: Assume that answer is $C(2n+1,2)-n=2n^2$ for odd vertices ,and for the maximum number of edges we have $n$ pairs of unconnected vertices. Inductive Step: Let $v_i,v_j$ be our extra vertices in order to prove for $2n+3$.From any $4$ vertices in the graph $G_{2n+1}$, exactly one pair can be chosen that is not connected. So for $G_{2n+3}$ we have to establish edge connections that include $v_i,v_j$. We have n unconnected pairs of vertices. If we connect $v_i,v_j$ with these pairs, we obtain $4n$ edges and if we connect $v_i,v_j$ with each other, we obtain $4n+1$ edges in total. Therefore, we obtain $2n^2+4n+1$ edges and since we can connect the only vertex outside of the n pairs with only one of $v_i$ and $v_j$, we obtain $2n^2+4n+2=2(n+1)^2$

I think I can't understand above. My answer is $674 \times 674 \times 675$ Tripartite(?) Graph gives the answer and the proof is by Turan obviously.

Lleeya wrote: I think I can't understand above. My answer is $674 \times 674 \times 675$ Tripartite(?) Graph gives the answer and the proof is by Turan obviously. My construction is maximal edge construction

Unfortunately, I am not able to understand anything from #2, even what of that is the answer. I believe the answer in #3 is correct, however Turan's theorem doesn't imply that. It only states the fact about the maximum number of $K_2$, while the problem asks $K_3$

Oh, I thought the problem was too easy haha, this may be the right proof. Get a random $K_3: \,\,i,j,k$ and let the set $I,J,K$ be the points that make a $K_3$ with $(j,k),(k,i),(i,j)$ let the set of rest points be $V$. Without loss of generality let $|I|\geq|J|\geq|K|$ If there is an edge $v_1,v_2$ in $I$ $v_1,v_2,j,k$ makes a $K_4$. So the number of $K_3$ is at most $|I||J||K|+|V| \frac{|I||J||K|}{|K|}=|I||J|(2023-|I|-|J|)$ which is trivially at most $674 \times 673 \times 675$.

Lleeya wrote: So the number of $K_3$ is at most $|I||J||K|+|V| \frac{|I||J||K|}{|K|}$ Can you please explain why?

We can solve this from proving the generalized version of Turan. Sorry for terrible writeup since I had to write in a hurry Generalized Turan wrote: Let $G$ be a simple graph. For $r \ge k$, if $G$ is $K_{r+1}$ free, then the maximum number of $k$ clique is $\binom{r}{k} \left(\dfrac{n}{r} \right)^k$. (or something similar depending on $n \mod r$ but... im too lazy) We prove this by induction on $k$ and $n$. Let $T_k(n,r)$ be the $r$ partite graph that the maximum number of $k$ clique is achieved. From maximizing, we can assume that there is a $r$ clique in $G$. $$\#[K_k] \le \sum_{0 \le i \le k}{ \binom{r}{i} \left(\dfrac{n-r}{r}\right)^i \cdot \binom{r-i}{k-i} } = \binom{r}{k}\left(\dfrac{n}{r} \right)^k$$Therefore, if for $i \le k$, $T_i(n-r,r)$ is the graph that maximum is achieved, then for $k,n,r$, this also holds. (Actually, we proved that the max value when $(n,r,k)$ is recursively calculated in terms of $(n-r,r,i)$ for $i \le k$. I will not add details on the exact value determined by $n \mod r$.) Now, when for $i < k$, the hypothesis holds then it also holds for $(n,k)$ for all $n$ since base case $n = 1$ is trivial. When $k = 2$, this is original Turan, which i will omit the proof. Hence, this will ensure that the inductive hypothesis (with a little more calculation for $n \mod r$ hehe) holds.

Seungjun_Lee wrote: $\binom{r-i}{k-i}$ Did you mean $\binom{r}{k-i}$? If negative, why should $r-i$ be there? Also, the current formula doesn't even output an integer. When you will add the $n\mod r$ part, how are you planning to prove the identity like $$\sum_{0 \le i \le k}{ \binom{r}{i} \left(\dfrac{n-r}{r}\right)^i \cdot \binom{r-i}{k-i} } = \binom{r}{k}\left(\dfrac{n}{r} \right)^k$$but with floors or other bad stuff?

Here, sunce we are K_{r+1} free, if we have i clique on the remaining part, we can only select among r-i points. If not, this will form a r+1 clique For floors or other stuff, we change the (n/r)^i to the quotient. This will make the same identity with some addition like (n mod r)Ci but this is easy to calculate. See the exact form for turans lemma which is too hard to write in a phone. For more, you can also use zykov's symmetrization

Seungjun_Lee wrote: Here, sunce we are K_{r+1} free, if we have i clique on the remaining part, we can only select among r-i points. If not, this will form a r+1 clique Yeah, thank you! Seungjun_Lee wrote: For floors or other stuff, we change the (n/r)^i to the quotient. This will make the same identity with some addition like (n mod r)Ci but this is easy to calculate. See the exact form for turans lemma which is too hard to write in a phone I believe you are right, but I still want to see the write up to be sure.