Tuymaada 2024/Senior P8 wrote: A graph $G$ has $n$ vertices ($n>1$). For each edge $e$ let $c(e)$ be the number of vertices of the largest complete subgraph containing $e$. Prove that the inequality (the summation is over all edges of $G$): \[\sum_{e} \frac{c(e)}{c(e)-1}\le \frac{n^2}{2}.\] I find this result surprising, and very beautiful. The tricky part of this problem is the equality case which is quite tight -- once you realized the equality case after working with smaller examples, it shouldn't be that bad to solve the problem because there's only so much things you can do to preserve the equality cases throughout, so you need to account for every possible cost contribution. We will prove a stronger result (including equality characterization). Claim. For any graph $G$ with $n \ge 2$ vertices, \[ \sum_e \frac{c(e)}{c(e) - 1} \le \frac{n^2}{2} \]where equality holds if and only if $G$ is a multi-partite graph where each parts have equal size. Proof. As in most graph theory problem, we'll proceed by induction on $n$. The base case $n = 2$ is easy to deal with, as the summation value is either $0$ or $2$, where equality holds iff the two vertices are connected, which is just $K_{1,1}$. Let $c_H(e)$ be the number of vertices of the largest complete subgraph of $H$ containing $e$. When $G'$ is a subgraph of $G$, then $c_G(e) \ge c_{G'}(e)$ since any clique of size $c_{G'}(e)$ in $G'$ must exist in $G$ and thus $\frac{c_{G}(e)}{c_G(e) - 1} \le \frac{c_{G'}(e)}{c_{G'}(e) - 1}$ for which we'll obtain \[ \sum_{e \in G'} \frac{c_G(e)}{c_G(e) - 1} \le \sum_{e \in G'} \frac{c_{G'}(e)}{c_{G'}(e) - 1} \]which means that it's better if we consider the summation into individual subgraphs. Equality holds if and only if $c_G(e) = c_{G'}(e)$ for all $e \in G'$. Let us now suppose that the statement is true for any $n < k$, we will prove that this statement is true when $n = k$. We may assume that $G$ is connected, since otherwise if $G = G_1 \sqcup G_2$, where $|V(G_1)|, |V(G_2)| < n$ then by inductive hypothesis \[ \sum_{e \in G} \frac{c(e)}{c(e) - 1} = \sum_{e \in G_1} \frac{c(e)}{c(e) - 1} + \sum_{e \in G_2} \frac{c(e)}{c(e) - 1} \le \frac{|V(G_1)|^2}{2} + \frac{|V(G_2)|^2}{2} < \frac{n^2}{2}. \]Take the largest clique $C$ in the graph which is of size $k \ge 2$. By definition, $k = \max_{e} c(e)$. Consider the graph $G' = G \setminus C$ which has $n - k$ vertices being induced subgraph of $G$ and thus by inductive hypothesis, \[ \sum_{e \in G'} \frac{c_G(e)}{c_G(e) - 1} \le \sum_{e \in G'} \frac{c_{G'}(e)}{c_{G'}(e) - 1} \le \frac{(n - k)^2}{2} \]Now, by definition, we have $c_G(e) = k$ for all edges $e$ in this clique $C$ of size $k$ which has $\binom{k}{2}$ edges and thus this gives a total contribution of \[ \sum_{e \in C} \frac{c_G(e)}{c_G(e) - 1} = \frac{k}{k - 1} \cdot \binom{k}{2} = \frac{k^2}{2} \]Finally, we need to account for all the edges in $E(G \setminus C, C)$, where $E(X,Y)$ is the set of all edges connecting vertices in $X$ and $Y$ in $G$. We'll first notice that $E(G \setminus C, C) \le (n - k)(k - 1)$ since otherwise if $E(G \setminus C, C) \ge (n - k)(k - 1) + 1$, by PHP there exists a vertex $v \in G \setminus C$ such that $v$ is connected to all vertices in $C$, and thus we have found a larger clique of size $k + 1$, which is $C \cup \{ v \}$, contradicting the fact that $C$ is the largest clique in graph. We know that \[ E(G \setminus C, C) = \bigsqcup_{v \in G \setminus C} E(v, C) \]and notice that in each $e \in E(v,C)$, there exists a clique of size $|\mathcal{N}(v)| + 1$ that contains edge $e$ where $|\mathcal{N}(v)|$ is the number of neighbors of $v$ in $C$. To see this, just consider the clique containing all neighbors of $v$ in $C$, along with $v$. Therefore, $c_G(e) \ge |\mathcal{N}(v)| + 1$ for each $e \in E(v,C)$. Now, we have \begin{align*} \sum_{e \in E(G \setminus C, C)} \frac{c_G(e)}{c_G(e) - 1} &= \sum_{v \in G \setminus C} \sum_{e \in E(v,C)} \frac{c_{G}(e)}{c_G(e) - 1} \\ &= \sum_{v \in G \setminus C} |\mathcal{N}(v)| \cdot \frac{|\mathcal{N}(v)| + 1}{|\mathcal{N}(v)|} \\ &= \sum_{v \in G \setminus C} |\mathcal{N}(v)| + 1 \\ &= |E(G \setminus C, C)| + n - k \le (n - k)k \end{align*}To sum up, we have \[ \sum_{e \in G} \frac{c_G(e)}{c_G(e) - 1} = \sum_{e \in G \setminus C} \frac{c_G(e)}{c_G(e) - 1} + \sum_{e \in C} \frac{c_G(e)}{c_G(e) - 1} + \sum_{e \in E(G \setminus C, C)} \frac{c_G(e)}{c_G(e) - 1} \le \frac{(n - k)^2}{2} + \frac{k^2}{2} + (n - k)k = \frac{n^2}{2}. \]as desired. Equality holds if and only if: Equality on inductive hypothesis on $G \setminus C$: Equality holds for $G \setminus C$, i.e. $G \setminus C$ is a multipartite graph where each parts have equal size, and $c_G(e) = c_{G \setminus C}(e)$ for any $e \in G \setminus C$. Equality on $E(G \setminus C, C)$: every vertices $v \in G \setminus C$ is connected to exactly $k - 1$ vertices in $C$, and $c_G(e) = k$ for all $e \in E(G \setminus C, C)$. Now, suppose that $G \setminus C$ is a multipartite graph with $n - k$ vertices and each part has size $d$. Take two vertices $u,v$ of different as $|\mathcal{N}(u) \cap \mathcal{N}(v)| \ge |\mathcal{N}(u)| + |\mathcal{N}(v)| - k = k - 2$, this means that there exists a clique of size $k$ in $G$ which contains $uv$, and hence $c_{G}(uv) \ge k$ and by maximality of $k$, $c_G(uv) = k$. This means $c_{G \setminus C}(e) = k$. But we know that since $G \setminus C$ is a multipartite where each part has size $d$, $G \setminus C$ has a clique of size $d$ and does not have a clique of size $d + 1$, i.e. $c_{G \setminus C}(e) = d$, i.e. we must have $d = k$. Now, take any $v \in C$. We claim that $v$ has exactly $\frac{n - k}{k} \cdot (k - 1)$ neighbors in $G \setminus C$, and all of the non-neighbors are on the same part. To see this, note that $|E(G \setminus C, C)| = (n - k)(k - 1)$ and if ther exists a vertex $v$ which has more than $\frac{n - k}{k} \cdot (k - 1)$ neighbors, then it has a neighbor in all $k$ parts of $K_{\ell, \ell, \dots, \ell}$ and thus this induces a $K_{k + 1}$, which is a contradiction. Therefore, all vertex $v \in C$ can only have neighbors in at most $k - 1$ of the parts, which gives us $v$ have at most $\frac{n - k}{k} \cdot (k - 1)$ neighbors in $C$, and thus equality must hold. Therefore, each of the non-neighbors of $v \in C$ in $G \setminus C$ lies on one part, and since every vertex in $G \setminus C$ has $k - 1$ neighbors in $C$, this means that each of these non-neighbors of $v$ are in different parts. To finish this, note that $G \setminus C = K_{\ell, \ell, \dots, \ell}$ where $\ell = \frac{n - k}{k}$ and from the above facts, the equality induces a multi-partite graph of where each parts have equal size of $\ell + 1$, as desired.

I agree that the result is very beautiful, but it was previously proposed at the 2023 Bulgarian Winter Math Competition. Unfortunately, I could not find it on AoPS, but here is a solution on @dgrozev's blog: https://dgrozev.wordpress.com/2023/02/05/turans-theorem-again-2023-bulgarian-winter-math-competition/

@above here goes Bulgaria Winter 2023 Grade 12 There are some other great solutions, a reference to an arxiv paper, etc.