The Brussels graph is the name given on the House of Graphs website to the quintic edge-girth-regular graph
constructed by Araujo-Pardo and Leemans (2022). It is illustrated above in a number
of bilaterally symmetric LCF embeddings.
E. Spence (private communication reported in van Dam and Haemers 2002) found exactly three graphs with the same graph spectrum
as the Wells graph by an exhaustive computer search.
Though not mentioned by Araujo-Pardo and Leemans (2022), the Brussels graph is isomoprhic
to one of these two graphs (E. Weisstein, Nov. 6, 2025). In particular,
it is the graph described by van Dam and Haemers (2002) that can be constructed from
the Wells graph by removing an edge
and its antipodal edge
(i.e., the edge whose vertices are at graph
distance 4 from the original edge vertices
and
) and adding new edges
and
.
The Brussels graph satisfies the rhombus constraints and contains no known unit-distance forbidden subgraph, yet appears not to be a unit-distance. A number of embeddings found from different initial embeddings by minimizing the sum of square deviations from unit edge lengths until a local minimum was reached are illustrated above.