# Relationship between triangle free graphs and their minimum degree

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!

• You want an upper bound on the minimum degree. The average degree is larger (or at least as large.) Look for upper bounds on the number of edges in a triangle free graph with $n$ vertices (complete bipartite...) and use that. Jul 16 '13 at 23:25
• It might be useful to consider two vertices of minimum degree joined by an edge. If the graph is triangle free that gets a bound close to what is suggested, but there is more lurking behind the example. Jul 17 '13 at 0:08
• Thanks for accepting the answer. I would still like to know more of the motivation and the corollary, even if it did not turn out to be much more interesting. Jul 19 '13 at 22:27

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!

• Given the elementary nature of the analysis in this answer, I would like to see the corollary mentioned in the question and how it is more interesting than the supposedly weaker alternative. Jul 17 '13 at 5:37
• Indeed, a couning argument might show something mildly stronger: a non bipartite graph which is triangle free has either a minimum degree less than 2n/5, or the graph is 2n/5-regular. This could well be part of an undergraduate graph theory course. Jul 17 '13 at 6:49
• Very nice. So in a graph with $n$ vertices and minimum degree $\delta$ every edge is in at least $2\delta-n$ triangles. It is possible to have $n=2\delta$ and no triangles but if $n \le 2\delta-1$ then every edge is in a triangle so there are lots of triangles. Jul 17 '13 at 6:55

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}, }

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}.$