5
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jul 16, 2013 at 23:25
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 17, 2013 at 0:08
  • $\begingroup$ 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. $\endgroup$ Jul 19, 2013 at 22:27

3 Answers 3

5
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 17, 2013 at 5:37
  • $\begingroup$ 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. $\endgroup$ Jul 17, 2013 at 6:49
  • $\begingroup$ 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. $\endgroup$ Jul 17, 2013 at 6:55
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.