Question about triangle-free graphs I'm asking for your help with this problem
"Let $G$ be a triangle-free graph with $\delta > \frac{2n}{5}$. Show that $G$ is bipartite."
Every book I read says it's obvious, but I can't see it why. I'm kind of stuck.
 A: Suppose by way of contradiction that $G$ is not bipartite, let $C$ be an odd cycle of minimal length $l$.
Every vertex outside of $C$ is adjacent to at most $2$ vertices of $C$. If a vertex is adjacent to at least three vertices we can find an odd cycle smaller than $C$, this would be a contradiction (try to prove this, it is a good exercise).
So what is the maximum sum of the degrees of the vertices in $C$ possible? it is less than or equal to $(n-l)\cdot2+2\cdot l=2n$, why? Since there are at most $(n-l)\cdot 2$ edges going out of $C$ and there are $l$ edges between vertices of $C$ (if there was an edge between non-consecutive vertices of the cycle, this would imply a smaller odd cycle) the sum is at most $2(n-l)+2l$ (the edges between edges of $C$ add $2$ to the sum of degrees). Therefore the sum of the degrees of the vertices of the cycle is at most $2n$. this implies there is a vertex with degree $\frac{2n}{5}$ or less(since the number of vertices in the cycle is $5$ or more).
A: Seeking a contradiction, assume $G$ is not bipartite.  Then $G$ has a cycle of odd length; let $v_0, v_1, \ldots ,v_{k}$ be the vertices of the cycle, in their respective order.  As some notation, let $N(v)$ denote the set of neighbors of $v$.  Then if $|i - j| >2$ (when taken $\mod(k)$), then we must have $N(v_i) \cap N(v_j) = \emptyset$ by the minimality of our cycle.  Moreover, since $G$ is triangle free, if $u$ and $v$ are adjacent, then $N(u) \cap N(v) = \emptyset$ as well.  If $k \geq 7$ then we have that $3$ and $4$ are a distance of more than $2$ away from $0$ when viewed $\mod(k)$.  Thus, we have  that $N(v_0) \cap N(v_3) \cap N(v_4)$.  However, this is impossible, since $N(v_i) > 2n/5$, so we would have $|N(v_0) \cup N(v_3) \cup N(v_4)| > 6n/5$.  Thus, we have that $k < 7$.  Since $k$ clearly cannot be $3$ ($G$ is triangle free), we must have $k = 5$. 
Viewing subscripts $\mod(5)$, we have that $N(v_i) \cap N(v_{i+1}) = \emptyset$ and $N(v_{i-1}) \cap N(v_i) = \emptyset$.  This then implies that $|N(v_{i-1}) \cap N(v_{i+1})| > n/5$.  Define $A_i = N(v_{i-1}) \cap N(v_{i+1})$ for each $i \in \{0,1,\ldots,4\}$.  Then we note that $A_i \cap A_j = \emptyset$ for $i \neq j$.  This, however, is a contradiction: the $A_i$ are pairwise disjoint sets, each with cardinality $> n/5$.  Thus, $G$ is not bipartite.
