The Gray graph is a cubic semisymmetric graph on 54 vertices. It was discovered by Marion C. Gray in 1932 (Bouwer 1968), and was first published by Bouwer (1968). Malnič et al. (2002) showed that the Gray graph is indeed the smallest possible cubic semisymmetric graph. It is illustrated above in a number of graph drawings.
It is the Levi graph of the Gray configuration.
The Gray graph has a single order-9 LCF notation ![[-25,7,-7,13,-13,25]^9](/images/equations/GrayGraph/Inline1.svg)
and five distinct
order-1 LCF notations.
The Gray graph is implemented in the Wolfram Language as GraphData["GrayGraph"].
The Gray graph has graph genus 7 (Marušič et al. 2005, Conder and Stokes 2019, Brinkmann 2020, Metzger and Ulrigg 2025),
girth 8, graph diameter
6, automorphism group of group
order 
,
and is the Levi graph of two dual, triangle-free, point-,
line-, and flag-transitive, non-self-dual 
configurations (Marušič
and Pisanski 2000). The symmetric graph drawing illustrated above is due to Marušič
and Pisanski (2000).
The Gray graph has graph spectrum
 |
The Gray graph can be constructed by taking three copies of the complete bipartite graph 
and, for a particular graph edge 
, subdividing 
in each of the three copies, joining the resulting three vertices to a new graph
vertex, and repeating with each graph edge.
The Gray graph is a unit-distance graph, as first shown by J. Tan (pers. comm., communicated by E. Pegg, Jr., Oct. 16, 2021) and subsequently by Berman et al. (2025), illustrated above at left and right, respectively.
Abreu et al. (2025) showed that the Gray graph is pseudo 2-factor isomorphic, meaning that all its 2-factors (spanning subgraphs
that are regular of vertex
degree 2) have the same parity of number of cycles.
Together with the Goedgebeur graph, it is one
of two counterexamples reported by Abreu et
al. (2025) to the conjecture of Abreu et al. (2008) that the utility
graph 
,
Heawood graph, and Pappus
graph are the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs.
