Take the 2-minute tour ×

Let $G=(V,E)$ be a graph. Let $t$ denote the number of triangles in the graph, and $x$ denote the number of pairs of distinct triangles that share an edge.
(For example in $K_4$ we have $t=4$ and $x=6$)
Define $\Delta_{e}= {\text {no. of triangles that use e}}$
Define $\Delta_{max}=\max_{e\in E} \Delta_{e}$

We have been able to show that $\frac {2x} {3t} \leq \Delta_{max}$ and one can see that this is tight ($\pm 1$) when $G$ is a complete graph.

The proof we have is fairly simple: view this as an optimization problem. We aim to maximize the $L_2$ norm of the vector $(\Delta_{e_1},\Delta_{e_2}, ... , \Delta_{|E|})$ subject to the constraints that the overall number of triangles is still $t$ and that for all $e\in E$ we have $0\leq \Delta_e \leq \Delta_{max}$.

My problem is that I'm convinced that there's a simpler straightforward proof. I feel in my bones that there's some simple counting argument hiding here, as the 2 in the numerator and 3 in the denominator of the bound must stem from the fact that we are discussing edges and triangles. They do so in our proof, but in a sort of roundabout way. Can anyone come up with a two-sentence proof for this bound?


share|improve this question

1 Answer 1

up vote 7 down vote accepted

Let $N~$ be the number of figures consisting of two triangles sharing an edge, with one of the vertices not on the common edge marked.

Clearly $N=2x$. Alternatively, start with one triangle, mark a vertex, add a second triangle to the opposite side. So $N\le 3t(\Delta_e-1)$. Which is now exact for complete graphs and sharpens your inequality.

share|improve this answer
Thanks, nice observation. (Our original proof did give a sharp bound, but we neglect the -1 during the calculation since we are interested in asymptotics anyway) –  Shir Dec 20 '11 at 14:32
Here's a published paper (DISC 2012) where we used this proof (Lemma 5.9). link.springer.com/chapter/10.1007%2F978-3-642-33651-5_14 Thanks again, Prof. McKay. –  Shir May 26 '13 at 7:23

Your Answer


