Let $T$ be a trianglefree 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!

$\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$ – Aaron Meyerowitz Jul 16 '13 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$ – The Masked Avenger Jul 17 '13 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$ – The Masked Avenger 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 trianglefree 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 $n2$, 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!

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$ – The Masked Avenger Jul 17 '13 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/5regular. This could well be part of an undergraduate graph theory course. $\endgroup$ – The Masked Avenger Jul 17 '13 at 6:49

$\begingroup$ Very nice. So in a graph with $n$ vertices and minimum degree $\delta$ every edge is in at least $2\deltan$ triangles. It is possible to have $n=2\delta$ and no triangles but if $n \le 2\delta1$ then every edge is in a triangle so there are lots of triangles. $\endgroup$ – Aaron Meyerowitz 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 trianglefree 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 = {205218}, ISSN = {0012365X}, 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\delta1 \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{2E}{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{2E}{n} \le \frac{n}{2}$
along with
 $n$ odd , $E \le \frac{n^21}{4}$ and $\delta'=\frac{2E}{n} \le \frac{n}{2}\frac{1}{2n}.$