In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal in 1970.

It is the smallest graph that is triangle-free, 4-regular, and 4-chromatic.

The Chvátal graph is triangle-free: its girth (the length of its shortest cycle) is four.

It is, as Chvátal observes, the smallest possible 4-chromatic 4-regular triangle-free graph; the only smaller 4-chromatic triangle-free graph is the Grötzsch graph, which has 11 vertices but has maximum degree 5 and is not regular.

-regular graph (except for odd cycles and cliques) has chromatic number at most

[2] In connection with these two results and several examples including the Chvátal graph, Branko Grünbaum conjectured that for every

[3] The Chvátal graph solves the case

[1] Grünbaum's conjecture was disproven for sufficiently large

by Johannsen, who showed that the chromatic number of a triangle-free graph is

is the maximum vertex degree and the

introduces big O notation.

[4] However, despite this disproof, it remains of interest to find examples such as the Chvátal graph of high-girth

-regular graphs for small values of

An alternative conjecture of Bruce Reed states that high-degree triangle-free graphs must have significantly smaller chromatic number than their degree, and more generally that a graph with maximum degree

and maximum clique size

of this conjecture follows, for sufficiently large

The Chvátal graph shows that the rounding up in Reed's conjecture is necessary, because for the Chvátal graph,

, a number that is less than the chromatic number but that becomes equal to the chromatic number when rounded up.

This graph is not vertex-transitive: its automorphism group has one orbit on vertices of size 8, and one of size 4.

The Chvátal graph is Hamiltonian, and plays a key role in a proof by Fleischner & Sabidussi (2002) that it is NP-complete to determine whether a triangle-free Hamiltonian graph is 3-colorable.

[5] The characteristic polynomial of the Chvátal graph is

The Tutte polynomial of the Chvátal graph has been computed by Björklund et al.

[6] The independence number of this graph is 4.