Goedgebeur Graph
The Goedgebeur graph is the 30-vertex cubic bipartite graph found by computer search by Goedgebeur (2015). It gives a counterexample to the conjecture of Abreu et al. (2008) that the utility graph K_(3,3), Heawood graph, and Pappus graph are the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs. Here, 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 (6,6,18), (6,10,14), (10,10,10), and (30) (Goedgebeur 2015).
The name was introduced by Abreu et al. (2023).
The Goedgebeur graph is also the Levi graph of the self-dual 15_3 Goedgebeur configuration.
Abreu et al. (2023) constructed the Goedgebeur graph from the Heawood graph and the Möbius-Kantor graph GP(8,3), 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).
A number of minimal 8-crossing embeddings of the Goedgebeur graph are illustrated above (E. Weisstein, May 2-6, 2026).
The Goedgebeur graph admits two distinct order-1 LCF notation embeddings, both bilaterally symmetric, illustrated above (E. Weisstein, May 2, 2026).
Two curved-edge embeddings are illustrated above. The left drawing, due to Marién Abreu, displays the (10,10,10) 2-factor as the three ovals. The oval pattern suggested a possible infinite family of analogous counterexamples, but the corresponding construction breaks down in larger cases, underscoring the isolated nature of the Goedgebeur graph. The right drawing is from Abreu et al. (2023).
Four unit-distance embeddings of the Goedgebeur graph are illustrated above (E. Weisstein, May 2, 2026).
The Goedgebeur graph will be implemented in a future version of the Wolfram Language as GraphData ["GoedgebeurGraph"].
See also
Bipartite Graph, Configuration, Cubic Graph, Goedgebeur Configuration, Gray Graph, Heawood Graph, Levi Graph, Möbius-Kantor Graph, Pappus GraphPortions of this entry contributed by Marien Abreu
Explore with Wolfram|Alpha
More things to try:
References
Abreu, M.; Diwan, A. A.; Jackson, B.; Labbate, D.; and Sheehan, J. "Pseudo 2-Factor Isomorphic Regular Bipartite Graphs." J. Combin. Th. Ser. B 98, 432-442, 2008.Abreu, M.; Funk, M.; Labbate, D.; and Romaniello, F. "A Construction for a Counterexample to the Pseudo 2-Factor Isomorphic Graph Conjecture." Disc. Appl. Math. 328, 134-138, 2023.Abreu, M.; Goedgebeur, J.; Jooken, J.; Romaniello, F.; and van den Eede, T. "The Gray Graph is Pseudo 2-Factor Isomorphic." 16 Apr 2025. https://arxiv.org/abs/2504.12095.Goedgebeur, J. "A Counterexample to the Pseudo 2-Factor Isomorphic Graph Conjecture." Disc. Appl. Math. 193, 57-60, 2015.House of Graphs. "Goedgebeur Graph." https://houseofgraphs.org/graphs/19288.Cite this as:
Abreu, Marien and Weisstein, Eric W. "Goedgebeur Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GoedgebeurGraph.html