Relationship between triangle free graphs and their minimum degree

Question

Let $T$ be a triangle-free graph on $n$ vertices with minimum degree $\delta$ (which can be $0$). How does one show that $n >2\delta -1$? It seems to be true for bipartite graphs, but I cannot see how to prove it for general triangle free graphs in general. The motivation behind this question is if this is solved, I will have a much more interesting corollary to garner from it. Thank you!

Answer 1

In addition to the literature mentioned in the other answers, one can try some arguments based on counting.

Let $u$ and $v$ be two of $n$ vertices in a triangle-free graph, and further assume they are distinct and connected by an edge, with degrees $c$ and $d$ and $c$ at most $d$. Then their neighborhoods are disjoint, so $c - 1 + d - 1$ is at most $n-2$, giving $2\delta \leq n$.

It might be fun to recreate the $2n/5$ result: here is a start. Take an odd cycle from a non bipartite graph with minimal cycle length. If the cycle length is $7$ or greater, show that three vertices will produce either a triangle, a shorter odd length cycle, or a degree at most $2n/5$. Try a similar analysis with a $5$-cycle. Enjoy!

Answer 2

If you can prove it for bipartite graphs, this follows in general, by the following theorem of the reference below: any triangle-free graph of min degree greater than $2n/5$ is bipartite.

@article {MR0340075, AUTHOR = {Andr{\'a}sfai, B. and Erd{\H{o}}s, P. and S{\'o}s, V. T.}, TITLE = {On the connection between chromatic number, maximal clique and minimal degree of a graph}, JOURNAL = {Discrete Math.}, FJOURNAL = {Discrete Mathematics}, VOLUME = {8}, YEAR = {1974}, PAGES = {205--218}, ISSN = {0012-365X}, MRCLASS = {05C15}, MRNUMBER = {0340075 (49 #4831)}, MRREVIEWER = {D. J. Kleitman}, }

Answer 3

This follows from familiar results once everything is untangled. Suppose we have a triangle free graph with $n=2m$ or $n=2m+1$ vertices. Then $\delta \le m$ so $2 \delta \le n.$ This follows from the comments below.

You wish to show:

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

Since $\delta$ is an integer this is the same as $2\delta \ \le n$ i.e. $\delta \le \frac{n}{2}.$ It is sufficient to prove $\delta' \le \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}.$