Lower bound for the largest number of triangles with a common edge

222 Views Asked by At

While self-learning an introductory graph theorey course, I ran into below after-class exercise following Mantel's theorem:

Exercise 1.1.9*. Prove that every $n$-vertex graph with at least $\left\lfloor n^{2} / 4\right\rfloor+1$ edges contains some edge in at least $(1 / 6-o(1)) n$ triangles, and that this constant $1 / 6$ is best possible.


Although I can't prove it, I did find it used and refered by numerous papers, tracing a stronger result in [EFR]:

Lemma 4 (Edwards). Every graph with $n$ vertices and $\left\lfloor n^{2} / 4\right\rfloor+1$ edges contains an edge common to at least $n / 6$ triangles.
Note. This result was conjectured by Bollobás and Erdós in [1]. To see that this is essentially best possible, consider the graph of order $n=6 k$ whose vertices are partitioned into six independent sets $X(r, c)(r=1,2, c=1,2,3)$ with cardinalities $$ \begin{aligned} &|X(2,1)|=|X(2,3)|=k-1, \quad|X(1,3)|=|X(2,2)|=k, \\ &|X(1,1)|=|X(1,2)|=k+1 . \end{aligned} $$ Join distinct sets $X(r, c)$ and $X\left(r^{\prime}, c^{\prime}\right)$ completely if either $r=r^{\prime}$ or $c=c^{\prime} .$ This gives a graph with $9 k^{2}+1=n^{2} / 4+1$ edges in which every edge is on at most $k+1$ triangles. To the knowledge of the authors, the proof of Lemma 4 has never been published. In his unpublished manuscript, Edwards proves a stronger result. Let $G$ be a graph with $n$ vertices and $m$ edges and let $f_{3}(G)$ denote the largest integer such that $G$ contains $f_{3}(G)$ triangles with a common edge. Set $$ c_{v}^{2}=\frac{1}{n} \sum_{i=1}^{n}\left(1-d_{i} / \bar{d}\right)^{2} $$ where $d_{1}, d_{2}, \ldots, d_{n}$ are the degrees of the vertices of $G$ and $\bar{d}=2 m / n$ is the average degree. Edwards proves that if $m \geqslant n^{2} /\left(4\left(1+c_{v}^{2}\right)\right)$ and $G$ is not bipartite, then $$ f_{3}(G) \geqslant \frac{2 m}{n}\left(1+c_{v}^{2}\right)-\frac{n}{3}=\frac{1}{2 m} \sum_{i=1}^{n} d_{i}^{2}-\frac{n}{3} . $$ As an immediate corollary, if $m>\left\lfloor n^{2} / 4\right\rfloor$ then $$ f_{3}(G) \geqslant \frac{2 m}{n}-\frac{n}{3} . $$ In particular, setting $\left.m=\rceil n^{2} / 4\right\rfloor+1$ we have the result quoted in Lemma $4 .$

I also find that the same result was independently proved in this article: N. Khadžiivanov and V. Nikiforov, Solution of a problem of P. Erdős about the maximum number of triangles with a common edge in a graph, $C .$ R. Acad. Bulgare Sci. $\mathbf{3 2}(1979)$ $1315-1318 .$ Although I couldn't find it either, and it's likely to be in Russian.

I wish someone can help me with this exercise, hopefully the above information would be of help to you.


I find a proof for the stronger result with no $o(1)$ term in https://arxiv.org/abs/math/0405080, but I am still looking forward to explanation for Erdos's original proof.