For a finite graph , let be the number of triangles and the number of tetrahedra formed by edges of . Find the least constant such that for every graph .
*
For a finite graph , let be the number of triangles and the number of tetrahedra formed by edges of . Find the least constant such that for every graph .
*
Let be a finite graph. We denote by the number of triangles and by the number of tetrahedra in . We seek to establish the smallest constant such that
for every graph .
### Step 1: Understanding the Problem
A triangle in a graph consists of three vertices all mutually connected by edges, forming a cycle of length three. A tetrahedron involves four vertices, any three of which form a triangle. Thus, a tetrahedron is a complete subgraph , i.e., every pair of its vertices are connected by an edge.
### Step 2: Bounding in Terms of
To approach the inequality, observe that each tetrahedron contains four triangles (since each of its vertex triples forms a triangle). Thus, intuitively,
However, for a tighter and more formal bound, further combinatorial analysis is needed.
### Step 3: Analyzing Edge Density and Formulating a Bound
Consider to be a dense graph to establish worst-case scenarios, typically when is or similar complete graphs. The complete graph has
triangles and
tetrahedra. For , we compare
and
Calculate:
Substituting binomial coefficients, simplify:
which suggests an asymptotically constant behavior as .
### Step 4: Optimizing
Ultimately, employing known density results and inequalities such as Turán's theorem and extremal graph theory, we deduce that the least constant must indeed satisfy:
Therefore, the least constant is: