# Extreme graph has two adjacent triangles.

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.

• 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$? – vxnture Apr 3 at 12:32
• @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. – 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.$$

So

$$\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, 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$$