If each edge of a graph $G=(V,E)$ belongs to exactly one triangle then $|E|=\omicron(n^{2})$.

Question

Given $\epsilon > 0$, prove the existence of a $n_\epsilon \in \mathbb{N}$ such that, if $G=(V,E)$ is a graph on $n > n_\epsilon$ vertices, and each edge of $G$ belongs to exactly one triangle, then $|E| \leq \epsilon n^2$.

My idea is to use the following lemma:

Triangle Removal Lemma. For every $\gamma > 0$, there exists $\delta = \delta(\gamma) >0$ such that for every graph $G$ at least one of the following is true:
(A) there exists $F \subset E(G), |F| \leq \gamma v(G)^2$, such that $G - F$ is triangle-free
(B) $G$ contains at least $\delta v(G)^3$ triangles

Given a graph $G$ with the stated property, my observation is that the number of triangles in $G$ is $\frac{|E|}{3}$. Set $\gamma = \frac{\epsilon}{3}$. If we can define $\delta$ and $n_\epsilon$ so that this number of triangles in $G$ is less than $\delta n^3$, then we would have forced $(B)$ not to occur (and $(A)$ to occur).

The property of $G$ also gives us a set $F \subset E(G)$, $|F| = \frac{|E|}{3}$, such that $G - F$ is triangle free (i.e. we remove an edge from each triangle). And so, since $(A)$ occurs, $\frac{|E|}{3} < \gamma n^2$ and thus $|E| < 3\gamma n^2 = \epsilon n^2$.

I get stuck trying to define $\delta$ and $n_\epsilon$. All I know is that $\frac{|E|}{3} < \delta n^3$, and the self-evident fact that $n_\epsilon$ cannot be whatever we like, since otherwise, with $\epsilon$ arbitrarily small and $|E| \leq \epsilon n^2$, $|E|$ might be $0$. I think there must be some lower bound of $|E|$ that I haven't figured out yet.

Answer 1

Observe that if $G$ has the property that each edge belongs to exactly one triangle, then any pair of vertices of $G$ may have at most one edge connecting them.

Let $\gamma > 0$ and $\delta$ be its associated $\gamma$. In order for $(B)$ to be false, you must have $|E|/3 < \delta |V|^3$, or

$$|E| < 3\delta |V|^3.\tag{1}$$

In light of the observation, we must have $|E| \leqslant \binom{|V|}2$. Now, given $\delta$, it's easy to see that for $|V|$ large enough we have $\binom{|V|}2 < 3\delta |V|^3,$ and hence $(1)$ must hold.

We have established then there is $n_\delta\in \Bbb N$ large enough for which $(A)$ must be true. In this case, $|E|/3 < \gamma |V|^2 \implies |E| < 3\gamma |V|^2$. But this is basically what we want.

Given $\epsilon$, take $\gamma = \epsilon/3$. Observe that

• $\gamma$ is given in terms of $\epsilon$;
• From the lemma, we may obtain $\delta$ in terms of $\gamma$; and
• From our observation above, we may obtain $n_\delta$ in terms of $\delta$.

It follows that $n_\delta$ may be given in terms of $\epsilon$, which concludes the proof.