In this note, a structural result for maximal
Kr-free graphs is proven,
which provides a simple proof of the Andrásfai–Erd
$
\delta > {\left( {1 - \frac{1}
{{r - \frac{4}
{3}}}} \right)}n
$
\delta > {\left( {1 - \frac{1}
{{r - \frac{4}
{3}}}} \right)}n
is (
r–1)-colourable.
Mathematics Subject
Classification (2000): 05C35 - 05C15 - 05C75