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.

  • $\begingroup$ Not sure if this is helpful, but it is not difficult to prove that the girth of $G$ is either $4$ or $5$. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – M. Winter Sep 11 '17 at 7:46
  • $\begingroup$ @M.Winter There are bigger than $2(n-l)$ edges between $V′$ and $C$. $\endgroup$ – Alex Ravsky Sep 11 '17 at 8:23
  • 1
    $\begingroup$ I see. I only read the $\geq$ but skipped over the "bigger" in front of it. Thank you. Amazing proof. $\endgroup$ – M. Winter Sep 11 '17 at 8:28
  • 1
    $\begingroup$ What intelligence! Amazing. $\endgroup$ – Sandeep Ipk Sep 13 '17 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.