Although its construction is folklore, it was named after Andries Brouwer and Willem H. Haemers, who proved its uniqueness as a strongly regular graph.

One of the simplest is as a degree-4 generalized Paley graph: it can be defined by making a vertex for each element in the finite field

This means that it has 81 vertices, 20 edges per vertex, 1 triangle per edge, and 6 length-two paths connecting each non-adjacent pair of distinct vertices.

[3] As a strongly regular graph with the third parameter equal to 1, the Brouwer–Haemers graph has the property that every edge belongs to a unique triangle; that is, it is locally linear.

Finding large dense graphs with this property is one of the formulations of the Ruzsa–Szemerédi problem.

[5] Although Brouwer writes that this graph's "construction is folklore", and cites as an early reference a 1964 paper on Latin squares by Dale M. Mesner,[1] it is named after Andries Brouwer and Willem H. Haemers, who in 1992 published a proof that it is the only strongly regular graph with the same parameters.

The Sudoku graph is derived from Sudoku puzzles by making a vertex for each square of the puzzle and connecting two squares by an edge when they belong to the same row, column, or

[7][8] In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.