Let $P(n)$ denote the following statement; if a simple graph $G$ with $\Big\lfloor \frac{n^2}{2} \Big\rfloor$ vertices satisfy the condition that in every set of $n$ vertices of $G$, there exists three vertices that form a triangle in $G$, then $G$ contain at least one $K_4$. We will prove by induction on $n$ that $P(n)$ is true for all $n\geq 4$.

Remark; we can change the base case to $n=3$ and it’ll be more trivial.

Variant of this problem: https://artofproblemsolving.com/community/u348103h1523710p9118022

i am tripping nvm

Claim: let $G$ be a graph with $2n^2$ vertices, if there is no $K_4$ subgraph of $G$, then there exist $2n$ vertices that doesn't contain a triangle. Proof: Induct on $n$ to prove this. For $n=1$, no $2$ vertices contain a triangle, so the claim holds. Suppose for $n=k-1\geq1$, the claim holds. For $n=k$, suppose the opposition that there doesn't exist a $K_4$ subgraph, but any $2n$ vertices contain a triangle. Let $V'$ be any set of vertices, $d_{V'}(v)$ denote the number of neighbors of $v$ that are in $V'$. By induction hypothesis, take $2(n-1)^2$ vertices and since there is no $K_4$ subgraph, there exist $2n-2$ vertices that contain no triangle. Let $H$ be that $2n-2$ vertices, and $S:=\{v|v\notin H,\ d_H(v)\leq1\}$. $\forall u, v\in S,\ u\neq v$, $H+u+v$ contains a triangle $T$, $T\cap H\neq3$ ($\because H$ doesn't contain a triangle) and $T\cap H\neq2$ ($\because d_H(u)\leq1,\ d_H(v)\leq1$), so $u, v$ are in $T$. $\Rightarrow u, v\in S,\ (u, v)\in E(G)$, which means $|S|\leq3$ since $G$ doesn't contain $K_4$ subgraph. $$\sum_{v\in H}d_{G-H-S}(v)=\sum_{v\in G-H-S}d_H(v)\geq\sum_{v\in G-H-S}2\geq2(2n^2-2n-1)$$By pigeonhole principle, $\exists v\in H$ s.t. $d_H(v)\geq\lceil\frac{2(2n^2-2n-1)}{2n-2}\rceil=2n$, and there exists a triangle $U$ in that $2n$ vertices. $U+v$ is a $K_4$, which get a contradiction. $\therefore$ the claim holds for $n=k$. By induction the claim holds $\forall n\in\mathbb Z^+$, and this problem is the case $n=1000$.