If $G$ is simple with $n$ vertices, doesn't have a triangle and the minimum degree is greater than $\frac{2n}{5}$, then $G$ is bipartite.

Let $G$ be a triangle-free simple graph whose minimum degree is $> 2n/5$. Assume that $G$ is not a $5$-cycle. Prove that $G$ is bipartite.

darij grinberg's note: This is claimed to be a result by Andrásfai, Erdős & Sós (1974) in the Wikipedia, but the reference (Andrásfai, B.; Erdős, P.; Sós, V. T. (1974), "On the connection between chromatic number, maximal clique and minimal degree of a graph", Discrete Mathematics, 8 (3): 205–218, doi:10.1016/0012-365X(74)90133-2) is not very readable.

I have been trying to prove this but don't have an intuition on how to start I think it can be proved by contradiction.

Solution 1:

Assume the converse. Then $G$ contains a cycle of odd length. Take a cycle $C$ of the smallest odd length $l$. Then $l\ge 5$ and $C$ is chordless (the latter means that if $v$ and $u$ are adjacent vertices of $C$ then they are consecutive in $C$). Let $V’$ be the set of vertices of $G\setminus C$. Then, $V' \neq \varnothing$ (else, $G$ would just be a single cycle, which easily yields a contradiction). Each vertex of $C$ is adjacent to more than $2n/5-2$ vertices of $V’$, so there are more than $l(2n/5-2)\ge 2(n-l)$ edges between $C$ and $V’$. Since $|V’|=n-l$, by the pigeonhole principle there exists a vertex $v\in V’$ adjacent to at least $3$ vertices of $C$. There exist two of them joined by a path in $C$ of odd length less than $l-2$. When we connect them with $v$ we obtain a cycle of odd length less than $l$, a contradiction.