Skip to main content
1 of 2
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

This follows from familiar results once everything is untangled.

You wish to show:

In a triangle free graph $2\delta-1 \lt n.$

A stronger result is $2\delta \ \le n$ i.e. $\delta \lt \frac{n}{2}.$ It is sufficient to prove $\delta' \lt \frac{n}{2}$ where $\delta' = \frac{2|E|}{n} $ is the average degree, since clearly $\delta \le \delta'.$

Turans theorem (proof at the link) has as a special case Mantel's theorem:

A triangle free graph on $n$ vertices has at most $\big\lfloor\frac{n^2}{4}\big\rfloor$ edges.

So the cases for a triangle free graph are

  • $n$ even , $|E| \le \frac{n^2}{4}$ and $\delta'=\frac{2|E|}{n} \le \frac{n}{2}$

along with

  • $n$ odd , $|E| \le \frac{n^2-1}{4}$ and $\delta'=\frac{2|E|}{n} \le \frac{n}{2}-\frac{1}{2n}.$
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104