# 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.

• Not sure if this is helpful, but it is not difficult to prove that the girth of $G$ is either $4$ or $5$. – Batominovski Aug 15 '17 at 15:40

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.
• I cannot see how the pidgeonhole principle gives you a vertex $v$ with three neighbors in $C$. If all vertices of $V'$ are adjacent to exactly two vertices of $C$, then there are $2(n-l)$ vertices between $V'$ and $C$, so the inequality is satisfied. I think this is no major problem to complete the proof as this creates just one more case to check. – M. Winter Sep 11 '17 at 7:46
• @M.Winter There are bigger than $2(n-l)$ edges between $V′$ and $C$. – Alex Ravsky Sep 11 '17 at 8:23
• I see. I only read the $\geq$ but skipped over the "bigger" in front of it. Thank you. Amazing proof. – M. Winter Sep 11 '17 at 8:28