15. C8 (POL) For a finite graph \( G \), let \( f(G) \) be the number of triangles and \( g(G) \) the number of tetrahedra formed by edges of \( G \). Find the least constant \( c \) such that 
\[ g(G)^{3} \leq c \cdot f(G)^{4} \text { for every graph } G \]
15. Denote by \( V_{1}, \ldots, V_{n} \) the vertices of a graph \( G \) and by \( E \) the set of its edges. For each \( i=1, \ldots, n \), let \( A_{i} \) be the set of vertices connected to \( V_{i} \) by an edge, \( G_{i} \) the subgraph of \( G \) whose set of vertices is \( A_{i} \), and \( E_{i} \) the set of edges of \( G_{i} \). Also, let \( v_{i}, e_{i} \), and \( t_{i}=f\left(G_{i}\right) \) be the numbers of vertices, edges, and triangles in \( G_{i} \) respectively. The numbers of tetrahedra and triangles one of whose vertices is \( V_{i} \) are respectively equal to \( t_{i} \) and \( e_{i} \). Hence 
\[ \sum_{i=1}^{n} v_{i}=2|E|, \quad \sum_{i=1}^{n} e_{i}=3 f(G) \quad \text { and } \quad \sum_{i=1}^{n} t_{i}=4 g(G). \]
Since \( e_{i} \leq v_{i}\left(v_{i}-1\right) / 2 \leq v_{i}^{2} / 2 \) and \( e_{i} \leq |E| \), we obtain \( e_{i}^{2} \leq v_{i}^{2}|E| / 2 \), i.e., \( e_{i} \leq v_{i} \sqrt{|E| / 2} \). Summing over all \( i \) yields \( 3 f(G) \leq 2|E| \sqrt{|E| / 2} \), or equivalently \( f(G)^{2} \leq 2|E|^{3} / 9 \). Since this relation holds for each graph \( G_{i} \), it follows that 
\[ t_{i}=f\left(G_{i}\right)=f\left(G_{i}\right)^{1 / 3} f\left(G_{i}\right)^{2 / 3} \leq \left(\frac{2}{9}\right)^{1 / 3} f(G)^{1 / 3} e_{i}. \]
Summing the last inequality for \( i=1, \ldots, n \) gives us 
\[ 4 g(G) \leq 3\left(\frac{2}{9}\right)^{1 / 3} f(G)^{1 / 3} \cdot f(G), \quad \text { i.e. } \quad g(G)^{3} \leq \frac{3}{32} f(G)^{4}. \]
The constant \( c=3 / 32 \) is the best possible. Indeed, in a complete graph \( K_{n} \) it holds that \( g\left(K_{n}\right)^{3} / f\left(K_{n}\right)^{4}=\binom{n}{4}^{3}\binom{n}{3}^{-4} \rightarrow \frac{3}{32} \) as \( n \rightarrow \infty \). Remark. Let \( N_{k} \) be the number of complete \( k \)-subgraphs in a finite graph \( G \). Continuing inductively, one can prove that \( N_{k+1}^{k} \leq \frac{k!}{(k+1)^{k}} N_{k}^{k+1} \).