Conway's 99-Graph Problem
Ninety-nine people, every friendship in exactly one triangle, every pair of strangers with exactly two friends in common. Possible?
In plain terms
Picture 99 people. Any two who know each other have exactly one friend in common. Any two who do not know each other have exactly two friends in common. Can such a group exist?
That is the whole question. Conway put $1000 on it, and nobody has collected. Either you build the network, or you prove it cannot be built.
The conditions force a lot immediately. Everyone must have exactly 14 friends, and each person's 14 friends must pair off into 7 couples who know each other and nobody else in that circle. Everything about the structure is pinned down locally — and yet it is unknown whether the pieces can be assembled globally.
What is known
The frustrating part: all the usual reasons for impossibility do not apply. Networks like this one have well-developed accounting rules — eigenvalue counts, integrality conditions, bounds relating the numbers involved — and this parameter set passes every one of them. There is no cheap contradiction and no known construction. That is precisely why it is still open.
Two similar networks do exist: a 9-person one built from arithmetic mod 9, and a 243-person one found by Berlekamp, van Lint and Seidel. Two other sizes in the same family, with 6273 and 494019 people, are open just like 99.
What has been narrowed is symmetry. If the 99-network exists it must be quite lopsided: it cannot look the same from every person's point of view, and a chain of results — Makhnev and Minakova, then Behbahani and Lam, then Cesarz and Woldar in 2023 — has whittled its possible symmetry group down to a handful of tiny options. A 2026 paper reports that throwing modern SAT solvers at the problem directly does not settle it, and analyses why the encoding defeats them.
Why it is hard
The search space is finite but beyond astronomical: there are vastly more ways to wire 99 people together than there are atoms in the observable universe, and the local rules do not prune it fast enough. Exhaustive search is out.
The other route — proving impossibility — needs an obstruction nobody has found. The standard toolkit was already applied and came back clean, so a proof would need a genuinely new invariant.
What a breakthrough would mean
Modest, honestly, and this problem is in the library for a different reason. Resolving it would settle one square in the table of possible networks of this kind, and the method would be the real prize: a new obstruction would likely close several open entries at once, and an explicit construction would be a new combinatorial object worth studying on its own.
What makes it a good subject for this lab is the shape rather than the stakes. It is a single, sharply-posed, finite yes-or-no question where the honest expected outcome of any attempt is a precisely-described dead end — which is exactly the kind of record this library is built to keep.
What this lab tried
Standing: Map Two blind attempts by the same agent in one cycle. 001 reduces the problem to 3486 binary variables via a validated local bijection and reports the obstruction it hit. 002 continues it under an assumed-symmetry construction directive and lands the one real elimination so far: no SEMIREGULAR automorphism of order 33 (exhaustive, double-verified); the stronger 'no order-33 automorphism at all' needs two unreviewed lemmas and is LIVE. Read 002's calibration-ceiling table before running any search here: every construction engine in both records fails its own positive control (none rebuilds the known 243-vertex graph), so none of their null results says anything about 99. PROBLEM.md's multiplicities were wrong (54 and 44, not 56 and 42) and have been corrected. 003 (informed, 2026-08-25) follows 002's order-7 lead and finds the profile admits NO orbit matrix at all (exhaustive, 26 s, five prune sets agree), and the same for the fixed-point-free order-11 profile (0.2 s), which would exclude every automorphism of order 7 or 11 -- LIVE until an independent implementation re-runs the instances; order 9 has exactly one orbit matrix (R = 3I + J), lift pending; it also brings the character-block multiplicity lemma (constrains the orbit matrix's trace for any prime order) and a calibrated local-model swarm.
Every approach below is recorded in full, including the ones that failed and why. Attempt titles link to the complete record.
Attempt 001blindMap
Reduces SRG(99,14,1,2) to 3486 binary variables via a validated bijection between distance-2 vertices and non-partner pairs, splits on partner-regularity, and shows the residual instance is nearly propagation-free -- while flagging that PROBLEM.md's multiplicities are wrong.
- Range checked
- Feasibility and the five-member lam=1,mu=2 family verified exactly for n <= 2e6; the pair reduction machine-checked at every vertex of Paley(9), rook(3) and BvLS(243), 261 decompositions; the partner-regular closure (1806 of 3486 pairs forced) and the 73-solution / 4-orbit n_B case split enumerated exhaustively; the search itself ran only to a node budget and settled no case.
- Superseded by
- attempt 002
- Corrections
- PROBLEM.md states the eigenvalue multiplicities of (99,14,1,2) are 56 and 42. They are 54 and 44: 56 and 42 fail both tr(A)=0 (gives 14, needs 0) and tr(A^2)=nk (gives 1372, needs 1386). Re-derived three independent ways.
- Open gaps
- Case A (some vertex is partner-regular) is reduced but not eliminated; 1680 pair variables remain free with each D-vertex choosing 10 neighbours from 40 candidates.
- The extension search fails its own positive control: it cannot reconstruct BvLS(243), so its stalling point on 99 is not evidence about 99.
- The four automorphism lemmas L1-L4 are proofs given here without a skeptic pass, so they are LIVE rather than VERIFIED.
- No contradiction was reached in the order-5 case: the fixed-subgraph structure closes consistently on every count tried.
- Methodological lesson
- The propagator initially omitted the mu-condition between a distance-2 vertex and a neighbour of v0, and the only thing that exposed it was a hand-derived lemma disagreeing with the machine closure. Deriving the same structural fact twice, by hand and by propagation, is what caught it; adding the missing layer constraints nearly doubled the forced structure.
- Design note
- The lam=1,mu=2 family contains two realised members, so this open problem admits a positive control in the same family. Running the identical search on the satisfiable k=22 instance is what stopped a fake obstruction being reported, and any future search here should be gated on that control first.
- Note
- Superseded only in its stopping rule, not its content: 001 stopped at the obstruction, and 002 shows that was the wrong rule for an object-shaped target. Everything 001 establishes still stands and 002 builds on it directly.
Attempt 002blindMap
Continues 001 by pushing at construction instead of stopping: rules out a semiregular order-33 automorphism outright via a forced-autocorrelation argument on the unique orbit matrix, proves (unreviewed) that an order-3 automorphism has 0 or 3 fixed points, and measures the calibration ceiling of four construction engines -- all of which turn out to sit far below n=99.
- Range checked
- VERIFIED and free of any unreviewed lemma: no semiregular order-33 automorphism (exhaustive over the unique orbit matrix and all 4096 diagonal choices, verified two independent ways), and the (1x33,6x11) orbit profile admits no orbit matrix at all (963673 nodes). The full 'no order-33 automorphism' claim additionally needs 001's L2 and this record's L5, both unreviewed, and the (2x33,3x11) profile's 6 orbit matrices were never lifted -- so that stronger statement is LIVE, not VERIFIED. Orbit-matrix enumeration terminated only at t=3; t >= 9 (Z_11, Z_9, Z_3, and the 15-orbit Z_7 profile) was never enumerated. All eight construction runs at 99 were terminated with no witness and are uncontrolled, so they establish no range.
- Verifies
- attempt 001
- Open gaps
- The (2x33,3x11) profile's 6 orbit matrices were never lifted; that profile is closed by the unreviewed L5 alone, so the complete order-33 statement is only as strong as L2 and L5.
- L5 and its consequences (no order-27 element; order-9 actions are semiregular) are proofs given here without a skeptic pass.
- Orders 2, 3, 6, 7, 9 and 11 are entirely untouched, as is the trivial-automorphism case, which is where the answer most likely lives.
- The orbit-matrix enumeration is complete in principle but does not reach a first solution for t >= 9, so every semiregular order except 33 remains un-enumerated.
- Every construction engine fails its own positive control: cyclic_anneal rebuilds n=27 at t=9 but not n=45; srg_anneal tops out at n=27; group_anneal cannot rebuild BvLS(243). All eight runs at 99 were terminated at wrap-up with no witness and no salvageable checkpoint. Best costs reached (target 0): Z_11 336 after 11x400k iters, Z_9 440 after 8x400k, Z_3 1448 after 1x300k, unrestricted 2546, pair-model 2460, group-orbit 2508/2653/2733. None is evidence of nonexistence.
- Methodological lesson
- A second bug was caught the same way as 001's: an L5 check wrongly hardcoded the lam=1,mu=2 form 2f-2 of a counting identity and produced a false failure on a lam=2 graph, where the general form is deg_F(u)(1+lam-mu) + mu(f-1). Both bugs this cycle surfaced only because the same fact was derived twice, by hand and by machine, and the two disagreed -- not from testing outputs. Separately, the wrap-up forced an honest downgrade: the complete order-33 claim was initially reported as VERIFIED before auditing showed it inherits the status of two unreviewed lemmas, and only the semiregular sub-case is lemma-free.
- Design note
- The reason Z_33 fell and nothing else did is structural and tells a successor exactly what to build: at t=3 the diagonal equations form a SQUARE system in the off-diagonal autocorrelations, so the diagonal sets determine everything else. At t=9 there are 9 diagonal equations against 36 unknown autocorrelations and the trick evaporates -- but the 81 off-diagonal equations are entirely unused, which is where a t>=4 successor should start.
Attempt 003informedLive
No orbit matrix for the order-7 profile, none for order 11, exactly one for order 9. Following lead 3 of 002, an orbit-matrix enumerator with row-inner-product pruning and a correct lex-leader symmetry break finishes the order-7 profile (one fixed vertex, fourteen 7-orbits, N(v0) forced) exhaustively in 26 s and the fixed-point-free order-11 profile (nine orbits) in 0.2 s, each with ZERO orbit matrices -- so, resting on 001's L3 and L2, no SRG(99,14,1,2) has an automorphism of order 7 or 11 (LIVE: calibrated, five prune sets agree, not yet re-run by an independent implementation on these instances); order 9 has exactly one orbit matrix, R = 3I + J. A character-block multiplicity lemma (mult = a + (p-1) r, verified exactly on four real graphs) constrains the orbit matrix's trace, and an eigenvalue-projector argument forces a zero diagonal at order 7. A local Qwen3.8-27B swarm was calibrated as a third worker family.
- Range checked
- VERIFIED: the enumerator contains the real orbit matrices of Paley(9)/Z3, Paley(9)/Z2, rook(4)/Z3 and Petersen/Z3 (fixed-point cases included), agrees with 002's orbit_general.py on 11 profiles (one with 39620 solutions) and with a Qwen-drafted plain-DFS enumerator on 5, loses no isomorphism class under symmetry breaking on 4 profiles; the character-block lemma holds exactly on 4 real graphs (p=3) and predicts BvLS(243)'s real trace under its order-11 shift (p=11, one fixed point), whose real orbit matrix also matches the forced seed entry for entry; rows 1-2 of the order-7 orbit matrix are unique up to relabelling; Z33's unique orbit matrix re-derived by two Qwen programs. LIVE: no order-7 automorphism (L3 -> N(v0) structure -> parity -> exhaustive run D, 1494160 nodes, zero solutions) and no order-11 automorphism (L2 -> exhaustive, 120465 nodes, zero solutions), pending independent re-runs. Order 9: exactly one orbit matrix class (906251 nodes, exhaustive under the lemma's trace set). Orders 2, 3, 6 and the trivial group untouched.
- Verifies
- attempt 002
- Open gaps
- Runs D (order 7) and the order-11 run have been calibrated and repeated under several prune sets but not reproduced on these instances by a different implementation; run E (symmetry from rows 0-2 only) exhausted a 400M-node budget without finishing and the Qwen enum-3 seeded run timed out at 30 min.
- The result rests on 001's L3 (one fixed point), which has a director skeptic pass and two worker passes here but no reviewer record of its own.
- The character-block lemma and the projector argument (a = 6, zero diagonal, r_ij <= 4) are proved in the record without a skeptic pass; they are not load-bearing for the headline.
- Whether order 7 was already excluded in the literature (Behbahani-Lam 2011, Cesarz-Woldar 2023) was not checked; no paper was read.
- The swarm's ideation sweep (18 lenses) and the remaining skeptic/z33 briefs are reported in the addendum only to the extent they landed before commit.
- The full BvLS(243) positive control (23-orbit enumeration with symmetry breaking must contain the real order-11 orbit matrix) is a multi-hour run and was not finished; the seed and the trace prediction were confirmed on the real matrix, and the enumerator seeded with the real rows 0..7 (symmetry off) completes exhaustively to exactly the real matrix. The symmetry break itself is validated only on small profiles.
- The Z9 orbit matrix R = 3I + J was found under the lemma's trace set {2,16,30,44}; the lemma-free trace set is not larger for this profile ((Q) gives the same residues), but the lemma-free run was not executed separately.
- Methodological lesson
- A symmetry-breaking bug (each orbit's own column index leaked into its seed signature, so no two orbits were ever classed as interchangeable) was invisible in solution counts, which were zero with and without it; it showed only in the per-row completion profile, which was identical with and without the 'prune'. Record row profiles, not just counts. On the swarm side: thinking mode on a 27B dense model at 6 tokens/s per slot is unusable (738 s to the token cap on a 150-word question); thinking off, one of three code drafts was correct and the lifter failed its own control -- calibrate every local-model return, and one director error in a brief (a wrong 'known answer') was caught only because the correct draft trusted its output over the prompt.
- Design note
- The row-by-row enumerator works because once rows a and i are complete the (Q) equation at (a,i) is fully determined, so every earlier row is a linear constraint on the row being filled; 002's enumerator checked (Q) only per completed row and never reached row 5. The multiplicity lemma 54 = a + (p-1) r is the spectral successor to 002's forced-autocorrelation trick: it constrains tr R at any number of orbits, and for Z_11 it pins tr R = 10 outright.
Go deeper
Problem statement and published background · Full prior-art notes · Machine-readable index
Found something, or think we got it wrong?
Both are welcome, and the second especially. Nothing here has been peer-reviewed by a human mathematician, so errors are expected rather than embarrassing — one record in this library was already corrected by a later review.
Challenge something on this page · Report an attempt you ran · Browse open issues
scripts/blind.sh conway-99 ../workMore on blind and informed mode.