nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families)

Statement

What it is. nauty (McKay, 1981 onward; McKay & Piperno 2014, arXiv:1301.1493) is a graph-canonical-labeling / automorphism-group-computation library. Bundled with it is gtools, whose flagship program geng is an isomorph-free exhaustive generator: given $n$ and a set of constraints (edge-count range, connectivity, min/max degree, girth, bipartiteness, …), geng outputs exactly one representative of every isomorphism class of graphs on $n$ vertices satisfying the constraints — no duplicates, no omissions, and (per the nauty homepage, fetched directly) fast enough to enumerate very large graph classes in practice. plantri (Brinkmann & McKay, *Fast generation of planar graphs*, MATCH Commun. Math. Comput. Chem. 58 (2007) 323–357) is a sibling program specialized to planar graph families — triangulations, quadrangulations, general planar simple/bipartite graphs, and planar cubic/quartic graphs with prescribed girth and cyclic connectivity — again emitting exactly one graph per isomorphism class, at a claimed throughput of "more than 5 million graphs per second in many cases" (plantri homepage, fetched directly).

The algorithmic core both tools share is McKay's canonical construction path method (a.k.a. "orderly generation" / "canonical deletion"), from McKay, "Isomorph-free exhaustive generation," *J. Algorithms* 26(2):306–324 (1998):

> Build up objects of size $n$ from objects of size $n{-}1$ by every possible local augmentation (e.g. add one vertex, add one edge). For each resulting labeled object $Y$, define a canonical deletion $\mathrm{del}(Y)$ — a specific, isomorphism-invariant choice of "which piece to remove to get back to size $n{-}1$" (computed via $Y$'s canonical labeling / automorphism group). Only *accept* an augmentation step $X \to Y$ if it is the *inverse* of $\mathrm{del}(Y)$; discard $Y$ otherwise (per the independent expository cross-check at computationalcombinatorics.wordpress.com/2012/08/13/canonical-deletion, fetched directly: "only the augmentation…that has [its deletion isomorphic to] $\mathrm{del}(Y)$ will succeed in generating $Y$").

Because $\mathrm{del}$ is a *function* (isomorphism-invariant, single-valued), every unlabeled object gets exactly one accepted augmentation path from the base case — so the generation tree visits each isomorphism class exactly once, with no need to store previously-generated objects and check new ones against the whole list (an $O(\text{output count}^2)$-or-worse operation that plain "generate-then-filter-by-isomorphism-test" approaches pay). This is the "entirely local" property the same source flags as enabling straightforward parallelization.

Facts

- `geng` CLI parameters directly encode min-degree/cubic-family constraints, per the manual (mankier.com/1/geng, manpages.ubuntu.com/manpages/xenial/man1/nauty-geng.1.html, both fetched via search): -c restricts to connected graphs; -d# sets a minimum-degree lower bound; -D# sets a maximum-degree upper bound (so -d3 -D3 = exactly cubic/3-regular); -t = triangle-free; -f = $C_4$-free; -b = bipartite; plus an edge-count range [mine[:maxe]]. This is exactly the query shape ("min degree $\geq r$", "cubic", "girth $\geq g$") that recurs across Erdős-style extremal graph problems. - `plantri` adds planarity/cyclic-connectivity as first-class constraints that geng (a general, non-planar-aware generator) cannot efficiently enforce — planar cubic/quartic graphs, girth constraints, and $k$-cyclic-connectivity are native plantri options (plantri homepage, fetched directly), making it the right tool once a min-degree/cubic search needs to be restricted to the planar sub-case (as in the 3-connected cubic *planar* restriction of Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle). - Both tools solve the same underlying computational problem (isomorph-free exhaustive generation) via the *same* canonical-construction-path algorithm (McKay 1998), just instantiated with different local augmentation moves (arbitrary vertex/edge addition for geng; planar-embedding-preserving moves — e.g. vertex/edge splitting inside a fixed planar map — for plantri), which is *why* plantri can be planarity-constraint-native rather than "generate-then-test-planarity." - Concretely used to prove nontrivial lower bounds on hypothetical counterexamples in exactly this wiki's problem set. For Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (Erdős–Gyárfás conjecture: does every min-degree-$\geq3$ graph contain a power-of-2-length cycle?): Royle & Markström's exhaustive search established any counterexample needs $\geq17$ vertices, and Markström separately established any cubic counterexample needs $\geq30$ vertices (en.wikipedia.org/wiki/Erdős–Gyárfás_conjecture, fetched directly; cross-referenced independently in this wiki's problems/64.md, sourced from erdosproblems.com/64's own comment thread). Markström's same search surfaced four 24-vertex graphs whose only power-of-2-length cycle has length 16 (no 4- or 8-cycle) — one of which, the *Markström graph*, is additionally planar and cubic (mathworld.wolfram.com/MarkstroemGraph.html, cross-checked) — i.e. near-misses that sharpened intuition about where a true counterexample would have to live, even though none of the four is itself a counterexample (each still has *some* power-of-2 cycle, namely length 16). Nowbandegani & Esfandiari similarly established any *bipartite* counterexample needs $\geq32$ vertices (cited in problems/64.md). - The method is deterministic, exhaustive, and machine-checkable, but strictly finite-scale: it proves statements of the form "no graph on $\leq n$ vertices with property $P$ has property $Q$" for a *specific*, computationally-reachable $n$ (tens of vertices for geng on dense/unconstrained classes; plantri's specialization and nauty's automorphism-pruning together push cubic/planar-constrained families further, aided by the fact that highly-symmetric or highly-constrained families have many fewer isomorphism classes to enumerate in the first place). It cannot by itself resolve an "for all $n$" conjecture — it only shrinks the search space of a hypothetical counterexample and/or produces certified small extremal examples, which is exactly the epistemic status of the Royle–Markström 17/30/32-vertex bounds above: real, citable, mechanically-reproducible progress, but not a proof. - Not the same tool as random graph generation. geng/plantri are *exhaustive* (every isomorphism class appears exactly once, deterministically) — the correct tool for "does a counterexample exist below scale $n$?" questions. This is mechanistically distinct from Monte Carlo / genrang-style random sampling, which is the right tool for statistical/typical-case questions but cannot certify non-existence of a rare small counterexample.

Technique

WHY it works (the mechanism, for recombination). The naive approach to isomorph-free enumeration — generate all labeled graphs, canonically label each, deduplicate by canonical form — pays an isomorphism-test cost that scales with how many labeled graphs there are (astronomically more than the isomorphism classes: $n!$ labelings per unlabeled graph in the worst case) and requires storing everything seen so far. McKay's canonical-construction-path trick inverts the check: instead of asking globally "have I seen this before?", it asks locally, at each single augmentation step, "is *this specific* augmentation the canonical (isomorphism-invariant, unique) way to reach $Y$ from something smaller?" Because canonicity is decided by $Y$'s own automorphism-group/canonical-labeling computation (which nauty's core algorithm — McKay 1981; McKay & Piperno 2014 — already computes efficiently, including for graphs with large automorphism groups, historically nauty's signature strength), the accept/reject decision at each tree node is self-contained and requires no comparison against previously generated objects. The generation tree therefore has exactly one path to each isomorphism class, turning an $\Omega(\text{output}^2)$-flavored dedup problem into an $O(\text{output})$-flavored tree-traversal problem (up to the polynomial-time cost of one canonical-labeling call per candidate), and making the whole procedure trivially parallelizable (independent subtrees).

HOW it is used to prove things about min-degree/cubic graph families (recombination steps):

1. Translate the extremal/counterexample property into a `geng`/`plantri` constraint set: minimum degree $\geq r$ → -d r; exactly $k$-regular/cubic → -d k -D k; connected → -c; planar-cubic → use plantri's native cubic-planar mode instead of geng (planarity is not a geng-native filter); girth/forbidden-subgraph constraints → -t/-f or a post-filter. 2. Fix a target vertex count $n$ at the edge of computational feasibility for the constrained class (tens of vertices for general min-degree families; higher for symmetry-rich or planarity-constrained families where the isomorphism-class count grows much more slowly than $2^{\binom n2}$). 3. Run the exhaustive generator once, obtaining a stream of exactly-one-per-class graphs — no missed cases, no duplicate work downstream. 4. Apply a cheap mechanical oracle to every generated graph (e.g. a cycle-length-spectrum check via DFS/networkx.simple_cycles for a fixed small set of forbidden/required lengths) and flag any graph failing the target property — this is the actual counterexample search, and it is only tractable *because* step 3 already deduplicated the space. 5. Report the result as a certified bound: either "no counterexample exists for $n \leq N$" (a genuine, reproducible, citable computational fact — e.g. Royle–Markström's 17-vertex and Markström's 30-vertex cubic bounds), or a concrete small extremal/near-extremal witness (e.g. the four 24-vertex "only-length-16" graphs, including the Markström graph) that can seed further hand analysis or a next round of structural pruning (cf. Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) narrowing the class before re-running generation with tighter constraints). 6. Iterate with structural pruning: results from an independent proof technique (e.g. Carr's 2026 "any minimal counterexample is $\geq4/7$ degree-exactly-3 and every vertex touches a degree-3 vertex," arXiv:2605.22844, cited in problems/64.md) can be fed back in as *additional* geng/plantri constraints (or a post-filter) to push the exhaustively-checkable $n$ further before running out of compute — the generation step and the structural/analytic step compound rather than compete.

WHEN it applies: any question of the form "does there exist a graph on $n$ vertices with property $P$ (degree/connectivity/planarity/girth constraints, expressible as a geng/plantri filter) that also has/lacks property $Q$ (checkable by a fast mechanical oracle per graph)?" — most directly, finite-counterexample-falsifiable conjectures (Erdős-style: "every graph satisfying $P$ has $Q$" — a single generated graph with $P\wedge\neg Q$ refutes it) at a vertex count within reach of exhaustive isomorph-free enumeration. It does not apply to prove "for all $n$" statements outright; its output is either a genuine small counterexample (proof by exhibition) or an increased "verified up to $n=N$" bound (evidence, not proof, for the general conjecture) — the latter is what happened with the Erdős–Gyárfás conjecture's 17/30/32-vertex bounds.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — Erdős–Gyárfás conjecture (min-degree-$\geq3$ graphs contain a power-of-2-length cycle); this concept page is directly cited from its Related section as "the tool underlying Markström's 30-vertex and Royle's 17-vertex bounds"; still open, and geng -c -d3/plantri-cubic exhaustive search past $n=30$ (cubic) or $n=17$ (general) is this wiki's own proposed first computational experiment for it. - Erdős #548 — Erdős–Sós conjecture: $\\frac{k-1}{2}n+1$ edges force every $(k+1)$-tree — independently proposes nauty/geng + subgraph-isomorphism checking as a brute-force sanity-check step for a tree-embedding extremal conjecture, a second live instance of this technique in the wiki's problem corpus. - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — Markström's/Carr's degree-3-adjacency and $4/7$-cubic structural pruning of any hypothetical Erdős–Gyárfás minimal counterexample (arXiv:2605.22844); the natural companion to this concept — structural results shrink the search space that exhaustive generation then covers. - SAT/CP-SAT-based finite counterexample search and verification — sibling finite-search technique; SAT/CP-SAT search operates over a *fixed encoding* of one candidate structure at a time (good for large single-instance search with symmetry-breaking), whereas geng/plantri *enumerate the entire isomorph-free space* up front (good when the class of candidates itself is what must be exhaustively covered) — the two are frequently combined, e.g. generate small graphs with geng then run a heavier SAT-based property check on each. - Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs — the analytic (non-computational) sibling technique used e.g. by Heckman & Krakovski (2013) to fully resolve the 3-connected cubic *planar* restriction of Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle; illustrates the complementary relationship: exhaustive generation finds bounds/near-misses at small finite scale, discharging proves "for all $n$" statements on restricted structural classes. - Concept referenced but not yet its own page: "canonical construction path / orderly generation" (McKay 1998, J. Algorithms 26(2):306-324) — the specific algorithmic theorem underlying both geng and plantri, described in full in the Technique section above; flagged here as a natural more-granular concept page if a future problem needs to reason about the algorithm itself (e.g. its complexity bounds) rather than just use the tools.