Given a simple graph with $n^3$ vertices. We know among every $n$ users, there is a $K_3$. Prove the graph contains a $K_5$. The bound is actually quite weak. In fact, it should hold for $\frac{n^3}{6}(1+o(1))$ vertices, but I don't prove this claim. Lemma: Let $G=(V,E)$ where $|V|\ge n^2$ and among any $n$ vertices, there exists a $K_3$. Then there is a $K_4$ in $G$. Proof: We induct on $n$. Fix a vertex $v$, and let $N(v)$ be the set of vertices adjacent to $v$. If $|N(v)|\ge n$, then there exists a $K_3$ in $N(v)$. Merge this $K_3$ with $v$ gives the desired $K_4$. Otherwise, there are at least $n^2-n$ vertices outside $v$ and $N(v)$. Pick $n-1$ of these vertices and $v$, and the $K_3$ must lie within the $n-1$ vertices. Therefore, the graph $G\backslash v\sqcup N(v)$ has $(n-1)n$ vertices, and there is a $K_3$ among any $n-1$ vertices. Now we induct on $n$ to solve the problem. If $|N(v)|\ge n^2$, then there exists a $K_4$ in $N(v)$. Merge this $K_4$ with $v$ gives the desired $K_5$. Otherwise, there are at least $n^3-n^2$ vertices outside $v$ and $N(v)$. Pick $n-1$ of these vertices and $v$, and the $K_3$ must lie within the $n-1$ vertices. Therefore, the graph $G\backslash v\sqcup N(v)$ has $(n-1)n^2$ vertices, and there is a $K_3$ among any $n-1$ vertices. This completes the induction.

Here is an approach that doesn't prove the existence of $K_4$ in the middle. Use induction on $n$, where the base case $n=3$ is trivial. If any $(n-1)$-element set has a 3-clique, then we obviously can induct down. Otherwise, consider a set $S$ of $n-1$ vertices that doesn't contain a 3-clique. Consider a vertex $v\notin S$ and look at $S\cup\{v\}$. We see that $v$ must be adjacent to at least two adjacent vertices in $S$. There are $n^3-n+1$ such vertices but $\tfrac{(n-1)(n-2)}{2}$ pairs. Thus, by pigeonhole, at least $n$ vertices in $G\setminus S$ are adjacent to the same two adjacent vertices $x,y\in S$. These $n$ vertices must form a 3-clique, so combining that 3-clique with $x,y$ gives a 5-clique.

Well basically induction and PHP, quite nice. I will instead prove the contrapositive statement: If there isn’t a $K_5$ in $G$, then there are $n$ vertices which don’t form a triangle. I will induct on $n$, the base case is trivial. Assume it’s true for $n$ and consider a graph $G$ with $(n + 1)^3$ vertices which doesn’t contain a $K_5$. Suppose FTSoC that any set of $n + 1$ vertices contains a triangle (*). Take a random subgraph with $n^3$ vertices (which again doesn’t contain a $K_5$) and apply the Induction Hypothesis to it. We obtain that we have $n$ vertices in $G$ which don’t form a triangle, but adding any other vertex to them makes a triangle; let the induced subgraph of those $n$ vertices be $M$ . There are $n^3 + 3n^2 + 2n + 1$ other vertices, and to each of them we will assign the edge from $M$ , with which it makes a triangle. If there are $e \leq \frac {n(n-1)}{2}$ edges in $M$ , then due to PHP, some edge $r$ has been assigned to at least $(n^3+3n^2+2n+1)/e>n+1$ vertices due to the mentioned above bound of $e$. Take those $n + 1$ vertices and apply the hypothesis (*) to obtain that there is a triangle in their induced subgraph. Note that this triangle has all its vertices connected to both ends of $r$ due to the choice of $r$, so this is a $K_5$, contradiction.

Even if we take an arbitrary vertex $n^2 $, it is not difficult to prove that $ K_4 $ is found in it. Similarly, $ K_5 $ is found between $ n ^ 3 $ vertex.

Same as Mark Bcc's. https://drive.google.com/file/d/1BpTMfyai7RfxOHPjEHXa7hSO0whxqWKS/view?usp=sharing

CLAIM 1::Among , every $n^2$ users , there is an ELMOclub with $4$ members Assume not , Let we have $n^2$ users such that the graph defined by then has no $K_4$ subgraph.Then for any vertex $v$ , $d(v)<n$ , otherwise we'll get a K4.Let $v_1$ be a vertex .Then there is a set $A_1$ of atleast $n^2-n$ vertices out of these $n^2$ such that none of then are adjacent to $v_1$.Let $v_2 \in A_1$ .Then there is a subset $A_2$ of $A_1$ of atleast $n^2-2n$ vertices such that none of them are adjacent to $v_2$.Since $n^2 =n \times n$ , in this way we get a set of $n$ vertices $\{v_1,v_2 ,\cdots v_n\}$ such that none of them are adjacent .This contradicts the question statement.Thus CLAIM proved. CLAIM 2::There is an ELMOclub with $5$ members Assume not .Then , by similar arguments , $d(v)<n^2$.Now , let $v_1$ be a vertex .Then there is a set $A_1$ of atleast $n^3-n62$ vertices such that none of then are adjacent to $v_1$.Let $v_2 \in A_1$ .Then there is a subset $A_2$ of $A_1$ of atleast $n^3-2n^2$ vertices such that none of them are adjacent to $v_2$.Since $n^3 =n \times n^2$ , in this way we get a set of $n$ vertices $\{v_1,v_2 ,\cdots v_n\}$ such that none of them are adjacent .Again , contra.hence proved.

Rephrase to graph theory, there are $n^3$ vertices, among any $n$ of them, there's a triangle and we need to show that there is a $K_5$. Claim: With the same condition, among any $n^2$ vertices, there is a $K_4$ Consider only the subgraph containing these vertices. If some vertex, say $v$ has degree $\ge n$, then among those there will be a triangle and so there is a $K_4$. If not, then there exist at least $n^2 - n > (n-1)^2$ vertices not connected to $v$. In those vertices, there are $(n-1)^2$ vertices and among any $n-1$ of them, there is a triangle (to show this, pick those $n-1$ as well as vertex $v$ but since $v$ isnt connected to any of them, the triangle will be among those $n-1$) so we may induct down and since the base case of $n = 3$ is true (in this case every three vertices form a triangle so its a clique), the claim follows. Now for the problem, we repeat the exact same argument. If there is a vertex, say $v$ of degree at least $n^2$, then by the claim we can find a $K_4$ in it and hence a $K_5$ including $v$. If not, then there are $n^3 - n^2 > (n-1)^3$ vertices at least not connected to $v$. And since among any $n-1$ of them, there must be a triangle (by the same reasoning as above), we can induct down and since $n = 3$ is true, the problem follows.

Assume the contrary, and consider the obvious graph interpretation. Then, there is no $5$-cliques, and for every $n$ vertices three of them forms a clique. Take the largest set $S$ of $k$ vertices containing no $3$-cliques. Then $k < n$. For two adjacent vertices $a, b$, we say that a vertex $v$ is a $\textit{common buddy}$ of $a,b$ if both are adjacent to $v$. We know that every vertex $v \not\in S$ must be a common buddy of some pair of adjacent vertices $a, b \in S$, otherwise adding $v$ into $S$ creates a larger set still with no $3$-cliques. On the other hand, for any pair of adjacent $a,b \in S$, if it has more than $k$ common buddies, then three of them, say $v_1, v_2, v_3$, must form a $3$-clique. But then $a, b, v_1, v_2, v_3$ are all pairwise adjacent, a contradiction. Hence, $a, b$ must have at most $k$ common buddies. But these two imply the number of vertices not in $S$ is at most $k\binom{k}{2} < n\binom{n}{2} = \frac{n^3 - n^2}{2}$, and we know there are exactly $n^3 - k > n^3 - n$ vertices. This easily gives a contradiction.

Here is a proof that uses the fact that $3+(3-1)=5$. View the problem as a graph in the obvious way. Let $m$ be the largest positive integer such that there exists a set of $m$ users without a triangle, so $m<n$. Let $S$ be such a set with $m$ vertices. By the maximality of $m$, adding any vertex to $S$ forms a triangle, so the following statement is true: For any $v \not \in S$, there exist $u,w \in S$ such that $u,v,w$ form a triangle. Given this, we can pair all $n^3-m$ vertices not in $S$ with an edge in $S$ (corresponding to $\overline{uw}$). By expectation, some edge $e=\overline{xy}$ in $S$ has at least $$\frac{n^3-m}{\binom{m}{2}}>\frac{n^3-m}{m^2/2}>\frac{n^3-n}{n^2/2}=2\left(n-\frac{1}{n}\right)>n$$vertices paired with it (here we can see that the bound is quite loose, and we can even make it looser with Turan's to replace $m^2/2$ with $m^2/4$). Thus, consider $n$ of the vertices paired with $e$. There exists some triangle with vertices $\{a,b,c\}$ within these $n$ vertices, whence $\{a,b,c,x,y\}$ clearly form a $K_5$. $\blacksquare$

The key lemma is a weaker version of St. Petersburg 2011.

I hope this works. Let $G$ be the simple graph where the vertices correspond two ELMOusers and the edges to pairs of ELMObuddies. We induct on $n.$ For $n=3,$ the conditions becomes: every $3$ vertices forms a $K_3;$ therefore the entire graph is a clique and we are done. Now assume the result holds for $n-1 \ge 3.$ If among any $n-1$ vertices there exist a $K_3,$ then we can induct down. Otherwise, consider a set $S$ of $n-1$ vertices such that the induced graph $G'$ on $S$ is triangle-free. Now let $i$ be any other vertex that is not in $S;$ then by hypothesis the induced graph on $S\cup \{i\}$ must contain a $K_3$ and it follows that there must be an edge on $G'$ such that $i$ connects to the two endpoints of these edge (beacause we are assuming $G'$ has not a triangle.) From the last paragraph, it follows that all the $n^3 - (n-1)$ vertices that are not in $S$ must connect to some edge in $G'$ (i.e. must connect to the two endpoints of that edge.) Therefore, it suffies to show that there exists three vertices not in $S$ forming a $K_3$ and such that they connect to the same edge in $G'.$ Indeed, by Turan's Theorem $G'$ has at most ${(n-1)^2}{/}{4}$ edges and hence one edge must connect to $n$ different vertices (this follows from Pigeonhole Principle since ${{(n-1)}^3}{/}{4} < n^3 - (n-1)$) hence by problems condition there must be a $K_3$ among these $n$ vertices. So done.

Here's a brute force solution with extremal arguments. Translate the problem to graphs. Out of all possible sets of $n$ vertices consider the one with the least number of triangles. Call that $S$. We know $S$ contains for sure a triangle. Now take the vertice in $S$ present in the biggest number of triangles in $S$. Let that vertice be $P$ and that number be $k$. Obviously, $k\ge 1$ . Remove $P$ from $S$. Now adding any new point from the rest $n^3-n$ into $S/P$ should yield at least $k$ new triangles. Otherwise, we would get a smaller total number of triangles in the new $S$. Thus, at least $(n^3-n)\cdot k$ triangles occur with exactly one side in $S/P$ and a vertice outside of $S$. Hence, since we only have $\binom{n-1}{2}$ sides, one side is present in at least $\dfrac{(n^3-n)\cdot k}{\binom{n-1}{2}}=\dfrac{2n(n+1)k}{n-2} > n$ triangles. Let that side be $ab$ and the corresponding points of the $n$ triangles be $Q={P_{1},..,P_{n}}$. By the condition we can find a triangle in $Q$. Let that be $P_{i1}P_{i2}P_{i3}$. Then, $a,b,P_{i1},P_{i2},P_{i3}$ is the answer.

Let $G$ be the social network and $G'$ be a induced subgraph of maximal size without a triangle. Obviously $|G'| < n$. Note that for every vertex $v \in G \backslash G'$, it forms a triangle with some other two vertices $s, t \in G'$, else adding $v$ to $G'$ preserves the no triangle property and thus violates maximality. Each vertex in $G\backslash G'$ with size $n^3 - |G'|$ can be assigned one of $\tbinom{G'}{2}$ edges to form a triangle with. Therefore, there is some edge which forms a triangle with at least\[\left\lceil \frac{n^3 - |G'|}{\binom{G'}{2}} \right\rceil \geq \left \lceil\frac{n^3 - n}{\binom{n}{2}}\right\rceil \geq 2n+2\]vertices in $G \backslash G'$. However, $2n + 2 > n > |G'|$ so for some edge $e \in G'$, we have a set with size $> |G'|$ that all form triangles with $e$. Yet, since this set has greater size than $G'$, we know that this set itself contains a triangle $a, b, c$, so simply choosing the five vertices $a, b, c$ and the endpoints of $e$ yields a $K_5$, done.

Stumper-scanning supplied subsequent solution. Sage suggestion: specific-seeming statement? Seek SUPER statements! SUPER Statement. Select $S \ge s \ge 2$, $\mathbf s \ge 1$, stick-&-stone sketch: $S^{\mathbf s}$ stones strong. Suppose selecting $S$ stones serves $s$ stones sustaining sticks supremely. Suddenly, see: $s + \mathbf s - 1$ stones sustaining sticks supremely! Solution. Scorn $\mathbf s = 1$: shallow statement! Stipulate $\mathbf s \ge 2$. Seek stone $\$$ sustaining $S^{\mathbf s - 1}$ supporting stones. Solution splits: Suppose seeking $\$$ successful. Simulate SUPER statement (substituting $\mathbf s - 1$), supplying $S^{\mathbf s - 1}$ stones supporting $\$$: secure $s + \mathbf s - 2$ stones sustaining sticks supremely. Suggest $\$$: sum $s + \mathbf s - 1$ stones, sustaining sticks supremely. Suppose stone $\$$ solely superstition: stones support sub-$S^{\mathbf s - 1}$ sticks. Select stones successively, shunning shared sticks. Simple statistics: sometime, $\left\lceil \frac{S^{\mathbf s}}{1 + (S^{\mathbf s - 1} - 1)} \right\rceil = S$ stones selected. SUPER statement suggests $S$ stones sustain some sticks: shoot! (Swear screening sucks...) Sacrificing statement strength, specifying $s = \mathbf s = 3$, supplies sought solution.

Let's give a big hand to CantonMathGuy on the prolific vocabulary of words starting with s! *Clap Clap Clap* (and the new solution) Here is the argument in a more readable language. Tip: When the statement is specific, seek generalizations and strengthen it. Strengthened argument: Let $n\ge t\ge 2, s\ge 1$. In a graph with $n^s$ vertices, if among any $n$ vertices, there is a $K_t$, then the graph with $n^s$ vertices contain a $K_{s+t-1}$ We induct on $s$. The base case, $s=1$, is true by definition. Henceforth assume $s\ge 2$. Case 1: There exists a vertex adjacent to at least $n^{s-1}$ neighbours. Among the $n^{s-1}$ neighbours, there is a $K_{s+t-2}$ by inductive hypothesis among the neighbours. Adding the vertex yields the $K_{s+t-1}$ Case 2: No vertex is adjacent to at least $n^{s-1}$ neighbours. I claim there exists an anticlique of size $n$. Take a random permutation of the vertices $v_1, \cdots, v_M$, and generate the anticlique this way: start a running counter $j=1$. Let $C$ be our current vertex set. If no vertex in $C$ is adjacent to $v_j$, then insert $v_j$ to $C$. Increment $j$ by 1. Let $1_v$ be an indicator for whether a vertex is in $C$. If it comes before its $\deg(v)$ neighbours, then it is in $C$, so $\mathbb{E}[1_v] \ge \frac{1}{\deg v+1}$. Then $\mathbb{E}[C] = \sum_v \mathbb{E}[1_v] \ge \sum_v \frac{1}{\deg(v)+1} \ge \frac{n^s}{n^{s-1}}=n$ Thus there exists an anticlique of size $\lceil \mathbb{E}[C] \rceil = n$. Contradiction!

SPHS1234 wrote: CLAIM 1::Among , every $n^2$ users , there is an ELMOclub with $4$ members Assume not , Let we have $n^2$ users such that the graph defined by then has no $K_4$ subgraph.Then for any vertex $v$ , $d(v)<n$ , otherwise we'll get a K4.Let $v_1$ be a vertex .Then there is a set $A_1$ of atleast $n^2-n$ vertices out of these $n^2$ such that none of then are adjacent to $v_1$.Let $v_2 \in A_1$ .Then there is a subset $A_2$ of $A_1$ of atleast $n^2-2n$ vertices such that none of them are adjacent to $v_2$.Since $n^2 =n \times n$ , in this way we get a set of $n$ vertices $\{v_1,v_2 ,\cdots v_n\}$ such that none of them are adjacent .This contradicts the question statement.Thus CLAIM proved. CLAIM 2::There is an ELMOclub with $5$ members Assume not .Then , by similar arguments , $d(v)<n^2$.Now , let $v_1$ be a vertex .Then there is a set $A_1$ of atleast $n^3-n62$ vertices such that none of then are adjacent to $v_1$.Let $v_2 \in A_1$ .Then there is a subset $A_2$ of $A_1$ of atleast $n^3-2n^2$ vertices such that none of them are adjacent to $v_2$.Since $n^3 =n \times n^2$ , in this way we get a set of $n$ vertices $\{v_1,v_2 ,\cdots v_n\}$ such that none of them are adjacent .Again , contra.hence proved. It can be strongly improved as the number of vertexes only connected to one point in the subset is limited!

Consider the obvious graph theoretic interpretation. We use induction on $n$ , with the base case $n=3$ being trivial. Assume that the statement is true for $n-1$. If all sets of $n-1$ vertices have a triangle in it we are done by the induction hypothesis. Assume henceforth that this is not true and let $\mathcal{S}$ be a set of $n-1$ vertices that don't contain a triangle. Consider a vertex $v \notin \mathcal{S}$. Notice that $v$ must be adjacent to two adjacent vertices in $\mathcal{S}$. There are $n^3-n+1$ vertices not in $\mathcal{S}$ and at most $\frac{(n-1)(n-2)}{2}$ possible pairs of adjacent vertices in $\mathcal{S}$ so, it follows by the pigeonhole principle that there is a set $T$ of $\frac{2(n^3-n+1)}{(n-1)(n-2)} \geq n$ vertices such that each vertex is adjacent to the same pair of adjacent vertices $(v_1, v_2)$ in $\mathcal{S}$. Recall that since $|T| \geq n$ there exists a triangle in $T$. Adding $v_1, v_2$ to this triangle obviously forms a 5-clique which is what we wanted to prove. $\blacksquare$

Probably same as the ones above, We use the induction on $n$ . The small cases we can verify by casework, For higher cases assume the contrary , Consider the obvious graph theory reprsenation. Pick any $A_{1},....,A_{(n-1)^3}$ vertices first , clearly there should exist a way to pick $n-1$ vertices from this such that if we pair them with $A_{(n-1)^3+1}$ then all the triangles in those $n$ vertices contain $A_{(n-1)^3+1}$ . Pick those vertices say $V_{1},....,V_{n-1}$, clearly for any vertex $V_i$ outside this there exists two $V_{j},V_{k}$ in those $n-1$ ones connected by a edge such that $V_{i},V_{j},V_{k}$ form a triangle. There are a total of $n^3-n+1$ ways to choose $V_i$ and a max of $\binom{n-1}{2}$ ways to pick $V_{j},V_{k}$ , So one choice of $V_{j},V_{k}$ repeats atleast $2\frac{n^3-n+1}{(n-1)(n)}$ times thats $ \geq n$ for all large $n$ Pick those $n$ ones say $B_{1},B_{2},....,B_{n}$ say the common pair for them is $V_{j},V_{k}$ Pick the triangle formed amongst $B$i's and pick $V_{j}$ and $V_{k}$ and u have a 5 clique