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$
4
  • 1
    $\begingroup$ Can you please write your inductive proof? (Your question may be voted to close because some users do not approve of questions that do not show attempts.) $\endgroup$ Jul 15 '20 at 12:02
  • 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 '20 at 13:11
  • $\begingroup$ @Batominovski Did you add the Ramsey theory tag? Does this question have some connection with Ramsey theory? $\endgroup$
    – bof
    Jul 17 '20 at 7:02
  • $\begingroup$ @bof I think it has, but if you disagree, feel free to remove the tag. I think you can rephrase the question like this: "how large (how many edges) a structure (a graph on $n$ vertices) has to be for a certain property (having $n$ triangles) to appear?" I actually wanted to make a question to generalize this question that makes it even more like a Ramsey theory problem, but didn't think it would receive any interest or that I would be knowledgeable about it to give enough context. $\endgroup$ Jul 17 '20 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.