Let $G$ contains $2n$ vertices and $n^2+1$ edges. G contains a triangle by Turan theorem.

Prove, that there is an edge that takes part in two or more triangles

If I assume the inverse, then every triangle has at most $2n-3$ edges going out of its vertices. Let there be $k$ triangles

That means, that we get a triangle-free part of the graph with $2n - 3k$ vertices and at least $n^2 - 2kn$ edges.

if $\left[\frac{(2n-3k)^2}{4}\right] \leq n^2-3kn$ then that means that the triangle-free part contains a triangle which leads to contradiction. But as I plotted the graphs I didn't find anything valuable.

May be the main fact is that the number of edges is exactly $n^2+1$, but I don't know how to use it.

  • $\begingroup$ What do you mean by "every triangle has at most $2n -3$ edges going out of its vertices"? Do you mean every vertex has degree at most $2n-3$? $\endgroup$ – vxnture Apr 3 at 12:32
  • $\begingroup$ @vxnture I mean that if $a,b,c$ are the degrees of the vertices making a triangle, then $(a-1)+(b-1)+(c-1) \leq 2n -3$. If the inequality doesn't hold then by Dirichlet (pigeonhole) principle there is a vertex that is conected with two vertices of the triangle. $\endgroup$ – Lada Dudnikova Apr 3 at 14:11

We prove a bit more general

Proposition. Let $n\ge 4$, $G$ be a graph with $n$ vertices and more than $ \lfloor n^2/4\rfloor$ edges. Then $G$ contains no triangles sharing an edge.

Proof. Suppose to the contrary that there are no triangles sharing an edge. Proceed as follows. As far as $G$ contains a triangle we remove its vertices from $G$. Assume we stopped when in $G$ remains $k$ vertices. Since $G$ became triangle-free, by Turán’s theorem, there remains at most $\lfloor k^2/4\rfloor$ edges.

Consider a graph $G$ at some step of the removal. Let $G$ contains $p$ vertices and $T$ be any triangle of $T$. Since $G$ contains no triangles sharing an edge, no vertex of $G\setminus T$ can be adjacent to two vertices of $T$. So when we remove vertices of a triangle $T$ from $G$ we remove at most $3+p-3=p$ edges. That is in total we have removed at most

$$n+n-3+\dots+k+3=\frac{k(n-k)}{3}+3\sum_{i=1}^{(n-k)/3} i=$$ $$\frac{k(n-k)}{3}+3\frac{\frac{n-k}{3}\left(\frac{n-k}{3}+1\right)}{2}=$$ $$\frac{k(n-k)}{3}\left(k+\frac{n-k+3}{2}\right)=$$ $$\frac{(n-k)(n+k+3)}{6}$$ edges of $G$. Thus $$\left\lfloor \frac{k^2}4\right\rfloor+\frac{(n-k)(n+k+3)}{6}>\left\lfloor \frac{n^2}4\right\rfloor.$$


$$\frac{k^2}4+\frac{(n-k)(n+k+3)}{6}\ge \frac{n^2-1}{4}+\frac{1}{4}$$

$$3k^2+2(n-k)(n+k+3)\ge 3n^2$$

This inequality transforms to

$$(k-3)^2\ge (n-3)^2.$$

Since $k\le n-3<n$, we have $k-3<0$, which easily implies $k=1$ and $n=4$. But then $G$ is a graph with four vertices and at least five edges, so it contains two triangles sharing an edge, a contradiction.$\square$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.