6
$\begingroup$

Let $n>1$ be an integer. A graph $G$ consists of $2n$ vertices and at least $n^2+1$ edges. Show that there exists at least $n$ triangles.

I already have a proof which is induction on $n$. But is there any direct method to do it?

UPDATE: Sketched inductive proof: Consider $n=k+1$ case. It can be shown there exists triangle $ABC$. Suppose in the rest of $2k-1$ points there are $P_A, P_B,P_C$ edges connecting to $A,B,C$ respectively.

  1. Case 1: $P_A+P_B+P_C \geq 3k-1$. It can be shown there are at least $k$ triangles taking one of $AB,BC,CA$ as edge, plus $ABC$, we get $k+1$ triangles.
  2. Case 2: $P_A+P_B+P_C \leq 3k-2$. Then one of $P_A+P_B, P_B+P_C,P_C+P_A$ must $\leq 2k-2$. Suppose $P_A+P_B \leq 2k-2$. One can show the other $2k-1$ points and C form a graph and have at least $(k+1)^2+1-(2k-2)-3=k^2+1$ edges ($3$ is from triangle $ABC$). By induction we have $k$ triangles, plus $ABC$, and we get $k+1$.
$\endgroup$
1
  • 2
    $\begingroup$ This was originally found by Rademacher (never published), then generaliezd by Erdos in "Some theorems on graphs" in 1955. It is also proven on the site few times, such as Graph with $2n$ vertices and $n^2+1$ edges has at least $n$ triangles. In all those cases, induction has been used (does not mean there is no non-inductive proof). $\endgroup$
    – Sil
    Jul 15, 2020 at 13:11

0

You must log in to answer this question.

Browse other questions tagged .