The Chvátal graph is a quartic graph on 12 nodes and 24 edges. It has chromatic number 4, girth 4, and graph crossing number 6.
Grünbaum conjectured that for every 
, 
, there exists an 
-regular graph with chromatic
number 
and girth at least 
. This result is trivial for 
or 
, but only a small number of other such graphs
are known, including the 12-node Chvátal graph,
21-node Brinkmann
graph, and 25-node Grünbaum
graph. The Chvátal graph is illustrated above in a number of drawings
(cf. Bondy; Knuth 2008, p. 39).
It has 370 distinct (directed) Hamiltonian cycles, giving a unique generalized LCF notation of order 4 (illustrated above), two of order 6 (illustrated above), and 43 of order 1.
The Chvátal graph has graph spectrum 
.
The Chvátal graph is implemented in the Wolfram Language as GraphData["ChvatalGraph"].
