Quickly proving the Andrásfai-Erdős-Sós-Theorem

Abstract

Given an integer $r\gs 2$, an important theorem first proved by B. Andrásfai, P. Erdős, and V. T. Sós states that any $K_{r+1}$--free graph on $n$ vertices whose minimum degree is greater than $(3r-4)n/(3r-1)$ is $r$--colourable, and determines the graphs that are extremal in this context. The purpose of this note is to give an alternative proof of this result using a different idea.

arXiv commentWithdrawn, since it turned out that the same proof was discovered earlier by Stephan Brandt, Combinatorica 23 (2003), no. 4, 693-696