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!
 A: 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!
A: 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},
}
A: 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}.$

