I am not sure if this works. But I will try anyway. Draw a graph and its vertices are the integers $1,2,.......,n$. An edge is drawn between $x$ and $y$ if and only if $(x,y)$ or $(y,x)$ belongs to $S$. For $3$-point subsets of $S$, call it good if any two points are connected by an edge. Denote $F(x)$ as the number of edges the vertex $x$ belongs to. Let $x$ be joined to $y$. We have that $F(x)+F(y)-2$ edges are attached to the other $n-2$ vertices and thus we also have at least $F(x)+F(y)-2-(n-2)$ vertices that are attached to both $x$ and $y$. Therefore we have at least $F(x)+F(y)-n$ good triples that contains $x$ as well as $y$. Hence the total number of good triples is at least: $\sum_{(x,y) \in S}\frac{F(x)+F(y)-n}{3}$. Now we have that $\sum_{(x,y) \in S}(F(x)+F(y)) = \sum^{n}_{x=1}d(x)^{2}$. Therefore $\sum_{(x,y) \in S}\frac{F(x)+F(y)-n}{3}= \frac{\sum^{n}_{x=1}F(x)^{2}-nm}{3}\geq \frac{(\sum^{n}_{x=1}F(x))^{2}}{3n}-\frac{nm}{3}= \frac{4m(m-\frac{n^{2}}{4})}{3n}$ as $\sum_{x=1}^{n}F(x) = 2m$.

shobber wrote: Let $S$ be a set consisting of $m$ pairs $(a,b)$ of positive integers with the property that $1 \leq a < b \leq n$. Show that there are at least \[4m \cdot \frac{(m-\frac{n^{2}}{4})}{3n}\] triples $(a,b,c)$ such that $(a,b)$, $(a,c)$, and $(b,c)$ belong to $S$. Don't you mean S is a set of sets of two elements $\{a,b\}$ (and not pairs, as $(a,b)$ and $(b,a)$ are distinct?) and we need to count the number of sets of three elements $\{a,b,c\}$ instead of triplets $(a,b,c)$? In fact we can prove the stronger statement, if $m > \frac{n^{2}}{4}$ (there is nothing to show in above problem, if $m \leq \frac{n^{2}}{4}$), then there are atleast $\lfloor\frac{n}{2}\rfloor$ such sets $\{a,b,c\}$ such that $S$ contains $\{a,b\}, \{b,c\}, \{a,c\}$

No, the problem is perfectly right.

Yeah, missed the $a < b$ condition (if not, we can find a counter example) Anyway, does not matter. Why do these olympiad question try to disguise well known graph theory problems in such silly ways? Cities with airplanes, pairs with $a < b$ etc. It is a rhetorical question. You don't have to answer.

TaiPan~SP! wrote: I am not sure if this works. But I will try anyway. Draw a graph and its vertices are the integers $1,2,.......,n$. An edge is drawn between $x$ and $y$ if and only if $(x,y)$ or $(y,x)$ belongs to $S$. For $3$-point subsets of $S$, call it good if any two points are connected by an edge. Denote $F(x)$ as the number of edges the vertex $x$ belongs to. Let $x$ be joined to $y$. We have that $F(x)+F(y)-2$ edges are attached to the other $n-2$ vertices and thus we also have at least $F(x)+F(y)-2-(n-2)$ vertices that are attached to both $x$ and $y$. Therefore we have at least $F(x)+F(y)-n$ good triples that contains $x$ as well as $y$. Hence the total number of good triples is at least: $\sum_{(x,y) \in S}\frac{F(x)+F(y)-n}{3}$. Now we have that $\sum_{(x,y) \in S}(F(x)+F(y)) = \sum^{n}_{x=1}d(x)^{2}$. I don't understand!! What is $d(x)$? Therefore $\sum_{(x,y) \in S}\frac{F(x)+F(y)-n}{3}= \frac{\sum^{n}_{x=1}F(x)^{2}-nm}{3}\geq \frac{(\sum^{n}_{x=1}F(x))^{2}}{3n}-\frac{nm}{3}= \frac{4m(m-\frac{n^{2}}{4})}{3n}$ as $\sum_{x=1}^{n}F(x) = 2m$.

Interpret as a graph in the obvious way as TaiPan did; we need to prove that a graph with $n$ vertices and $m$ edges has at least $4m\cdot\frac{(m-\frac{n^{2}}{4})}{3n}$ 3-cliques. Let $f(G(n,m))$ be the number of such cliques for such a graph $G(n,m)$ and $g(G(n,m))$ be the number of triples of vertices s.t. exactly two pairs of them are connected. Lemma: $g(G(n,m))\le m \left(n-1-\frac{2m}{n}\right)$. Proof: Let $a(V)$ be the set of vertices adjacent to vertex $V$, $d(V)$ its degree; it is apparent that $\sum d(V) = 2m$. Then we find that \[g(G(n,m))=\sum_{X,Y\in G,X\not \in a(Y)}|a(X)\cap a(Y)|\le \sum_{X,Y\in G,X\not \in a(Y)} \min\{d(X),d(Y)\}\] The last term, were it not to take the minimum of each pair, counts a vertex $V$ with degree $d(V)$ exactly $n-1-d(V)$ times. But the larger degree isn't counted in each pair, so it's bounded above by \[\frac{1}{2}\sum d(V)(n-1-d(V))\le \frac{n}{2} \cdot\frac{2m}{n}\left(n-1-\frac{2m}{n}\right)\] the last inequality following from Jensen's. Now notice that $3f(G(n,m))+g(G(n,m))=\sum \binom{d(X)}{2}\ge m\left(\frac{2m}{n}-1\right)$ again from Jensen's. Thus \[f(G(n,m))\ge \frac{m}{3}\left(\frac{2m}{n}-1\right) - \frac{g(G(n,m))}{3}\] Using our lemma, this is bounded below by \[\frac{m}{3}\left(\frac{2m}{n}-1\right)-\frac{m}{3}\left(n-1-\frac{2m}{n}\right)=4m\cdot\frac{(m-\frac{n^{2}}{4})}{3n}\] as desired.

Can we use Mantel Theorem to solve this problem? Mantel Theorem states that: " Given a graph $ G $ with $ n $ points and $ e $ edges, if $G $ doesn't contain any triangle then the maximum value of $ e $ is $ \left[\frac{n^2}{4}\right] $

Oh, I see. Mantel's theorem is just Turan's theorem for $k=3$. I don't believe that this problem is solvable through Mantel's, since if you look at the $m-\frac{n^2}{4}$ term, it's actually a stronger result. If you try to go the "naive" route of removing $\frac{4m}{3n}\left(m-\frac{n^2}{4}\right)$ edges to create a $3$-free graph and bounding the edges using Turan's, it leads nowhere, and sharper bounding on the fewest edges one would need to remove seems to be as difficult as the problem itself.

We basically need to show that the graph with $k$ edges and $n$ vertices has at least $ \frac{k(4k-n^2)}{3n} $ triangles We label the points $ 1 , 2 , 3 ..... , n $ and let point $i$ have degree $ d_i $(number of edges) . then if $i$ and $j$ are joined they have at least $d_i + d_j -2 $ other edges between them and these edges join then to $n-2$ other points . So there must be at least $d_i + d_j - n $ triangles which have $ i $ and $j$ as two vertices . Hence the total number of triangles must be at least $ \sum (d_i + d_j - n )/3 $ . But $ \sum ( d_i + d_j) = \sum (d_i)^2 $ because each point in $i$ occurs in just $ d_i $ terms . Thus the total number of triangle is at least $ \frac{\sum (d_i)^2}{3} - \frac{nk}{3} $ . But $ \sum (d_i)^2 >= \frac{ (\sum d_i )^2}{n}$ ( can be proved using chebyshev's inequality ) $= \frac{4k^2}{n}$ HENCE PROVED $ QED $ :Idea

robinson123 wrote: Can we use Mantel Theorem to solve this problem? Mantel Theorem states that: " Given a graph $ G $ with $ n $ points and $ e $ edges, if $G $ doesn't contain any triangle then the maximum value of $ e $ is $ \left[\frac{n^2}{4}\right] $ do you can point out the case of equal? And prove its?

shivangjindal wrote: We basically need to show that the graph with $k$ edges and $n$ vertices has at least $ \frac{k(4k-n^2)}{3n} $ triangles We label the points $ 1 , 2 , 3 ..... , n $ and let point $i$ have degree $ d_i $(number of edges) . then if $i$ and $j$ are joined they have at least $d_i + d_j -2 $ other edges between them and these edges join then to $n-2$ other points . So there must be at least $d_i + d_j - n $ triangles which have $ i $ and $j$ as two vertices . Hence the total number of triangles must be at least $ \sum (d_i + d_j - n )/3 $ . But $ \sum ( d_i + d_j) = \sum (d_i)^2 $ because each point in $i$ occurs in just $ d_i $ terms . Thus the total number of triangle is at least $ \frac{\sum (d_i)^2}{3} - \frac{nk}{3} $ . But $ \sum (d_i)^2 >= \frac{ (\sum d_i )^2}{n}$ ( can be proved using chebyshev's inequality ) $= \frac{4k^2}{n}$ HENCE PROVED $ QED $ :Idea I am not getting which part implementing $a<b$ case here Can anyone explain how he is saying this - Quote: So there must be at least $d_i + d_j - n $ triangles which have $ i $ and $j$ as two vertices .

@above: Take two adjacent vertices, with degrees $d_i$ and $d_j$. There are $n-2$ vertices excluding the two vertices then there are at least $(d_i -1) + (d_j-1) -(n-2)$ triangles

I do not understand how this follows from Jensen's: \[\frac{1}{2}\sum d(V)(n-1-d(V))\le \frac{n}{2} \cdot\frac{2m}{n}\left(n-1-\frac{2m}{n}\right)\]

shivangjindal wrote: We label the points $ 1 , 2 , 3 ..... , n $ and let point $i$ have degree $ d_i $(number of edges) . then if $i$ and $j$ are joined they have at least $d_i + d_j -2 $ other edges between them and these edges join then to $n-2$ other points . So there must be at least $d_i + d_j - n $ triangles which have $ i $ and $j$ as two vertices . Hence the total number of triangles must be at least $ \sum (d_i + d_j - n )/3 $ . But $ \sum ( d_i + d_j) = \sum (d_i)^2 $ because each point in $i$ occurs in just $ d_i $ terms . Thus the total number of triangle is at least $ \frac{\sum (d_i)^2}{3} - \frac{nk}{3} $ . But $ \sum (d_i)^2 >= \frac{ (\sum d_i )^2}{n}$ ( can be proved using chebyshev's inequality ) $= \frac{4k^2}{n}$ I still don't get how there are at least $d_i+d_j-n$ triangles as well. IF someone can explain that part of shivangjindal's proof, that would also be great!

We use the obvious graph theoretic interpretation. The key idea is that the number of triangles involving the edge $vw$ is at least $\mathrm{deg}(v)+\mathrm{deg}(w)-2n$. We then see that thrice the number of triangles is at least \begin{align*} \sum_{vw\in E}(\mathrm{deg}(v)+\mathrm{deg}(w)-n)&=\sum_{v\in V}\mathrm{deg}(v)^2-mn \\ &\ge n(2m/n)^2-mn, \end{align*}which gives the desired result.

Interpret the problem in terms of graph theory. Consider a vertex $v$ with neighbors $N(v)=\{w_1,w_2,\dots,w_{\text{deg}(v)}\}.$ Since the graph has $n$ vertices, each element $w_i$ of $N(v)$ is connected to at least $\text{deg}(w_i)-(n-\text{deg}(v))$ other elements of $N(v).$ Therefore, since summing over all vertices counts each edge twice, the number of triangles passing through $v$ is at least $$\frac{1}{2}\sum_{w\in N(v)}(\text{deg}(w)-(n-\text{deg}(v)))=\frac{1}{2}\left(\sum_{w\in N(v)}\text{deg}(w)-n\cdot\text{deg}(v)+\text{deg}(v)^2\right).$$Summing over all $v,$ we find that the number of pairs $(T,v)$ where $T$ is a triangle passing through a vertex $v,$ is at least $$\frac{1}{2}\left(2\sum_{v\in G}\text{deg}(w)^2-2mn\right)\ge\frac{(\sum_{v}\text{deg}(v))^2}{n}-mn\ge\frac{4m^2}{n}-mn.$$But since triangles have three vertices, the number of pairs $(T,v)$ is simply three times the number of triangles. Thus, the number of triangles in $G$ is at least $$\frac{1}{3}\left(\frac{4m^2}{n}-mn\right)=\frac{m}{3n}(4m-n^2),$$as desired.

Let $e=\{u,v\}$ be an arbitrary edge. There are at least $\deg u+\deg v-n$ triangles that $e$ is part of by pigeonhole principle. Hence, there are at least \[\frac{\displaystyle\sum_{u\in G}(\deg u)^2-mn}{3} \ge \frac{4m^2}{3n}-mn/3=\frac{m}{3n}(4m-n^2)\]triangles as desired.

Very standard result; I'm surprised I didn't know of this earlier. Obviously, count triples of edges that form a triangle. For each edge $e = uv$, there are $\deg u + \deg v - n$ vertices that are connected to both $u$ and $v$. Thus the number of triangles is $$T = \frac{\sum_{uv \in E} (\deg u + \deg v - n)}3 = \frac{\sum_v (\deg v)^2 - mn}3 \geq \frac m{3n}(4m-n^2)$$by C-S as needed.

For any edge $uv$, there are at least $\text{deg}(u)-1+\text{deg}(v)-1-(n-2)=\text{deg}(u)+\text{deg}(v)-n$ triangles with $uv$ as an edge. Hence there are at least $$\frac{1}{3}\sum_{\text{edge uv}} (\text{deg}(u)+\text{deg}(v)-n) = \frac{1}{3}\left(\sum_{\text{vertex v}} \text{deg}(v)^2 - mn\right) \ge \frac{1}{3}\left(n\left(\frac{2m}{n}\right)^2-mn\right) = \frac{1}{3}\left(\frac{4m^2}{n} - mn\right)$$ as desired, where the main inequality step follows from Jensen/QM-AM.

Convert to graph theory: Revised statement wrote: Prove that a graph with $m$ edges and $n$ vertices has at least \[\frac{m}{3n} (4m^2-n^2)\] triangles. For each edge $e = vw$, we consider the vertices $v$ and $w$ that make up the edge. By Pigeonhole, there are at least $\deg v + \deg w - n$ shared vertices between $v$ and $w$, and that translates to at least $ \tfrac{1}{3} (\deg v + \deg w - n)$ triangles for all $m$ edges. Thus, in the entire graph there are at least \[\sum_{e} \frac{\deg v + \deg w - n}{3} = \sum_{v} \frac{(\deg v)^2}{3} - \frac{mn}{3}\] since a vertex with degree $x$ gets counted $x$ times. However, C-S gives \[(\underbrace{1 + \cdots + 1}_{n \text{ times}})\left(\sum_{v} (\deg v)^2 \right) \ge \left(\sum_v \deg v \right)^2 = (2m)^2,\]\[\implies \sum_{v} (\deg v)^2 \ge \frac{4m^2}{n}.\] Plugging this into our equation for the number of triangles yields \[\sum_{v} \frac{(\deg v)^2}{3} - \frac{mn}{3} \ge \frac{4m^2}{3n} - \frac{mn}{3} = \frac{m}{3n} (4m^2-n^2),\] as desired. $\square$