The Goedgebeur graph is the 30-vertex cubic bipartite graph illustrated above in a number of embeddings (cf. Goedgebeur 2015, Abreu
et al. 2023). It was found by computer search by Goedgebeur (2015) and gives
a counterexample 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. The name was introduced by Abreu et al. (2023).
A 2-factor is a spanning 2-regular subgraph, i.e., a disjoint union of cycles covering all vertices. A graph is pseudo 2-factor isomorphic if all its 2-factors have the same parity of number of cycles.
The Goedgebeur graph has 45 edges, girth 6, graph diameter 5, cyclic edge-connectivity 6, and automorphism
group order 144. It has 312 2-factors, with cycle lengths 
, 
, 
, and 
(Goedgebeur 2015).
Abreu et al. (2023) constructed the Goedgebeur graph from the Heawood graph and the Möbius-Kantor graph 
, the Levi
graphs of the Fano configuration and Möbius-Kantor configuration, respectively.
Aside from the Gray graph, the Goedgebeur graph is
the only known counterexample to the pseudo 2-factor isomorphic graph conjecture
(Abreu et al. 2025).
The Goedgebeur graph will be implemented in a future version of the Wolfram Language as GraphData["GoedgebeurGraph"].
