Finding Every Smallest C6-Saturated Graph

Draw eleven dots. Connect fourteen pairs. Can you arrange the edges so there is no cycle of length six, but adding any missing edge creates one?

Here is such a graph.

For one quick check, add the missing edge between 0 and 1. It closes the path 0–10–6–8–4–1 into a six-cycle. The graph has 41 missing edges, and each one has to pass the same kind of check. Separately, the graph must not contain a six-cycle to begin with. (Induced or not: extra edges among a cycle’s vertices do not stop it from counting.)

This property is called C6-saturation. The saturation number, sat(n, C6), is the smallest number of edges in a graph with n vertices having that property.

The drawing gives an upper bound: sat(11, C6) is at most 14. Showing that 14 is the minimum requires a second argument. Finding every graph that attains the minimum requires a third.

An example small enough to inspect

The graph’s long chains make its cycle structure manageable. Compress each path whose internal vertices have degree two into a weighted edge, with its length as the weight. The remaining branch vertices are 0, 1, 2, and 3.

Any cycle that enters the interior of one of those chains must follow the whole chain. Enumerating cycles in the small weighted core therefore gives the possible lengths in the original graph: 4, 5, 7, 8, and 9. Six is absent.

For the other half of the check, the certificate supplies a five-edge path between the endpoints of every missing edge. Symmetry reduces the 41 pairs to 19 representative cases. Adding the missing edge closes the corresponding path into a six-cycle.

The published note and archive contain the complete paths and symmetry argument. The graph is also available as House of Graphs 58088.

That one witness also contradicts a small-order computational claim in Remark 1 of Zhang, Luo, and Shigeno’s 2015 paper, which reports 15 at order 11. Their general upper-bound theorem is unaffected. The separate exhaustive search establishes that 14 is minimal and that this is the unique minimum graph up to relabeling.

What the enumeration found

Here is what the search found. A minimum class means one graph shape, with all relabelings counted together.

Not all of this is new, and I want to be exact about which parts are. The value 16 at order 12 was already reported in the final 2015 paper; what I add there is the complete family of 35 minima. Lan and coauthors' 2025 work already supplies matching upper bounds at orders 12 through 15. What the exhaustive lower bounds add at orders 13 through 15 is exactness.

I have gotten this wrong before. My July post called the order-9 and order-10 values new. They weren’t: those values and their minimum families were already known. The current release corrects that.

The expensive half of a minimum

To prove sat(15, C6) = 20, a 20-edge witness supplies one direction. The other direction requires ruling out every graph on 15 vertices with fewer edges.

The enumeration uses nauty’s graph generator to produce unlabeled simple graphs over the relevant edge ranges. It imposes no connectivity or minimum-degree restriction. Two separate property-checking implementations reject all 784,526,109 graphs through 19 edges. Together with the 20-edge witness, that establishes the minimum.

Order 14 adds another layer. After excluding smaller edge counts, both implementations inspect 342,260,293 graphs with 19 edges and retain the same 205 witnesses. Every retained graph then receives further checks, including decoding its stored representation, verifying saturation, and checking that the family has no isomorphic duplicates.

A result like this can fail in at least three ways. A checker can misidentify a six-cycle. A generator can omit a graph. A file can contain something other than the object described in the paper. Running the same calculation twice catches none of these.

So the archive includes independent property checks, exact witness files, enumeration logs, and source hashes. Per-edge counts also agree with a separate exact-integer counting calculation using Pólya–Burnside theory. Count agreement is a useful check on the enumeration, but cannot by itself establish completeness: omissions and duplicates could cancel.

The two large enumeration streams share nauty’s generator. Their agreement is independent checking, not independent generation. The result is a reproducible computational proof, with those dependencies exposed; it is not a Lean proof or a SAT proof trace.

What a complete family lets us ask

The minimum-class counts jump around: 1, 35, 4, 205. I don’t know why yet. A single representative per order would have hidden that entirely.

Among the 205 order-14 minima, 113 have a leaf, a vertex incident to exactly one edge. The other 92 have minimum degree two. That suggests structural questions about attaching leaves and preserving saturation. At present it is a description of this finite family, not a general construction theorem.

This is where I want the work to go next. The enumeration gives a collection of exact objects. Explaining why they have these shapes, and which features survive at larger orders, is the next mathematical problem.

This account follows the October 18 v5 release. The work used substantial AI assistance for research code, checks, and exposition under my direction; the archive preserves the computational evidence and prior-work attribution.