It is the smallest 4-regular graph of girth 5 with chromatic number 4.

[2] It has book thickness 3 and queue number 2.

[3] By Brooks’ theorem, every k-regular graph (except for odd cycles and cliques) has chromatic number at most k. It was also known since 1959 that, for every k and l there exist k-chromatic graphs with girth l.[4] In connection with these two results and several examples including the Chvátal graph, Branko Grünbaum conjectured in 1970 that for every k and l there exist k-chromatic k-regular graphs with girth l.[5] The Chvátal graph solves the case k = l = 4 of this conjecture and the Brinkmann graph solves the case k =  4, l = 5.

Grünbaum's conjecture was disproved for sufficiently large k by Johannsen, who showed that the chromatic number of a triangle-free graph is O(Δ/log Δ) where Δ is the maximum vertex degree and the O introduces big O notation.

[6] However, despite this disproof, it remains of interest to find examples and only very few are known.

The chromatic polynomial of the Brinkmann graph is x21 - 42x20 + 861x19 - 11480x18 + 111881x17 - 848708x16 + 5207711x15 - 26500254x14 + 113675219x13 - 415278052x12 + 1299042255x11 - 3483798283x10 + 7987607279x9 - 15547364853x8 + 25384350310x7 - 34133692383x6 + 36783818141x5 - 30480167403x4 + 18168142566x3 - 6896700738x2 + 1242405972x (sequence A159192 in the OEIS).

The Brinkmann graph is not a vertex-transitive graph and its full automorphism group is isomorphic to the dihedral group of order 14, the group of symmetries of a heptagon, including both rotations and reflections.

The characteristic polynomial of the Brinkmann graph is