Conways 99 graph problem

952 Views Asked by At

The Conway 99 graph problem is stated here as one of 5 problems. My question is this: Is there somewhere a list of examples with "Conway graphs" with fewer then 99 vertices? Or can you provide examples with fewer than 99 vertices?

Definition of "Conway graph": It is a simple undirected graph $G=(V,E)$ with the following property:

(1) $\forall (x,y) \in E: \exists ! z \in V: (x,z),(y,z) \in E$

(2) $\forall (x,y) \in E^c: \exists ! (z,w) \in V \times V: (x,z),(x,w),(y,z),(y,w) \in E$

(The definition is from here: https://arxiv.org/pdf/1707.08047.pdf )

The Conway 99 graph problem asks if there exists a "Conway graph" with 99 vertices.

I am searching for examples of "small" Conway graphs.

Edit: Given the answer below, the next non trivial graph with 9 vertices is: $G(2,1)$ http://mathworld.wolfram.com/GeneralizedQuadrangle.html

or the same graph: $T(3,3)$: http://mathworld.wolfram.com/TorusGridGraph.html

This paper of Berlekamp might also be of interest where the graph with $243$ vertices is constructed.

1

There are 1 best solutions below

3
On BEST ANSWER

I don't know why people downvoted this question; it's perfectly valid and quite interesting to wonder why such a problem is listed by Conway and how difficult it might be.

This blogpost by Adam Goucher discusses briefly at the start some of what led to the problem, before leading onto his discovery of this lovely beast. You see from it that such graphs can only have $|V|\in\{3,9,99,243,6273,494019\}$ and that examples of 3, 9 and 243 vertices are indeed known (with the 243 vertex one being rather special!).

Hope this helps!