The 
-Andrásfai
graph is a circulant graph on 
nodes whose indices are given by the integers 1, ..., 
that are congruent to 1 (mod 3).
The Andrásfai graphs have graph diameter
2 for 
,
and the 
-Andrásfai
graph has 
proper 3-colorings for 
,
with three labeled colors. Up to a permutation of
colors, all these colorings are equivalent under its automorphism
group (Godsil and Royle 2001, pp. 119-120).
The following table summarizes the first few Andrásfai graphs.
 | name | circulant notation |
| 1 | 2-path graph |  |
| 2 | 5-cycle graph |  |
| 3 | 4-Möbius ladder |  |
| 4 | 4-Andrásfai graph |  |
| 5 | 5-Andrásfai graph |  |
| 6 | 6-Andrásfai graph |  |
The 
-Andrásfai
graph has independence polynomial
 |
with corresponding recurrence equation, for 
, given by
 |
