21
$\begingroup$

99-Graph: Is there a graph with 99 vertices in which every edge (i.e. pair of joined vertices) belong to a unique triangle and every nonedge (pair of unjoined vertices) to a unique quadrilateral?

$\endgroup$
  • $\begingroup$ To guarantee the "every" and "unique" conditions is not easy. $\endgroup$ – Rupei Xu Apr 6 '14 at 7:40
  • 5
    $\begingroup$ Professor John Conway (Princeton University) would like to offer $1,000 for this problem to the one who first solves it. $\endgroup$ – Rupei Xu Apr 9 '14 at 6:21
  • 3
    $\begingroup$ What does "belong to a quadrilateral" mean? If $x,y$ are non-adjacent vertices, do you mean there exists vertices $u,v$ such that $xu$, $uv$, and $vy$ are edges? $\endgroup$ – D.W. Jun 15 '17 at 18:07
  • 2
    $\begingroup$ I've got 99 vertices, but an edge ain't one. $\endgroup$ – Somatic Custard Aug 29 '18 at 14:18
  • 2
    $\begingroup$ It might be useful to clarify the conditions (especially the quadrilateral one; at first, I thought it was essentially a condition on the complement graph, that every non-edge was part of a non-edge quadrilateral, not a diagonal of a quadrilateral). It has been years since the question and accepted answer, though... $\endgroup$ – user44191 Aug 29 '18 at 17:14
29
$\begingroup$

First we will prove the graph is regular.

Let $x,y$ be two non-adjacent vertices, and let $a,b$ be their common neighbours. Define $X$ to be the neighbourhood of $x$ other than $a,b$, and $Y$ to be the neighbourhood of $y$ other than $a,b$.

Considering the edge $ax$, there is a unique vertex $u\in X$ adjacent to both of them. Considering the non-edge $yu$, there must be exactly one edge from $u$ to $Y$. Similarly for the common neighbourbour of $b$ and $x$. For a vertex in $v\in X$ not adjacent to $a$ or $b$, the two common neighbours of $v$ and $y$ must lie in $Y$.

Consider the bipartite graph with parts $X,Y$ and the edges between them. We have proved that each part has 2 vertices of degree 1 and the others of degree 2. This is only possible if $|X|=|Y|$, which proves that $x$ and $y$ have the same degree. This proves the graph is regular. A simple count shows the degree must be 14.

Now you are looking for a strongly-regular graph of order 99, degree 14, $\lambda=1$ and $\mu=2$. According to Andries Brouwer's table, the existence is unknown.

$\endgroup$
  • $\begingroup$ Can you say why a and b are unique? (I'm thinking of a red-blue complete graph where the red edges form triangles and the blue edges form quadrilaterals. Maybe that is the wrong picture?) $\endgroup$ – The Masked Avenger Apr 6 '14 at 15:46
  • $\begingroup$ @The Masked Avenger: If I understand the question correctly, any two non-adjacent vertices lie on a unique quadrilateral, which means they have exactly two common neighbours. There are no edge colours. $\endgroup$ – Brendan McKay Apr 6 '14 at 16:00
  • $\begingroup$ Also, for x and y not connected, I am getting that the sum of their red degrees is at least 90. Am I doing something wrong? $\endgroup$ – The Masked Avenger Apr 6 '14 at 16:10
  • $\begingroup$ I see. I thought the edge was part of the (blue) quadrilateral. Certainly your view is more intriguing. Thanks. $\endgroup$ – The Masked Avenger Apr 6 '14 at 16:12
  • $\begingroup$ Thank you for your helpful analysis and references. Life is so beautiful with a nice Professor like you! $\endgroup$ – Rupei Xu Apr 9 '14 at 6:20
-3
$\begingroup$

I claim that this paper contains a solution of the problem. Unfortunately, Conway's email account is inactive and I do not know how to reach him via the Internet.

01.09.2018

To clarify, I notice that the problem has two different interpretations:

(1) It is not important whether the set of nonedges is empty or not; in particular, a solution without nonedges would be acceptable.

(2) The set of nonedges must be nonempty.

If we choose (1) - and that's what I did - then my paper does provide an affirmative answer to the problem. Indeed, from Proposition 1 it follows that the number $99$ is good, i.e. there exist $\frac{99\cdot 98}{6}=1617 $ triangles such that every edge in $K_{99}$ belongs to a unique triangle. Further, the set of nonedges in $K_{99}$ is empty and therefore there is no requirement about quadrilaterals. Thus the desired graph is the complete graph $K_{99}$.

On the other hand, if we choose (2) the situation is more complicated because the following question arises:

What does "belong to a quadrilateral" mean?

Please, give me a definition.

05.09.2018

According to Gordon Royle's comment below, Conway's problem can be stated as follows:

Is there a graph with $99$ vertices in which every pair of joined vertices have one common neighbour and every pair of unjoined vertices have two common neighbours?

If so, I must acknowledge that I misread the problem and thus the question is still open.

P.S.: The problem that I solved is the following one:

Are there $n_1$ triangles and $n_2$ quadrilaterals such that every edge in the complete graph $K_{99}$ belongs either to a unique triangle or to a unique quadrilateral?

(In particular the equality $3n_1 +4n_2 =4851$ must hold.) My paper provides a solution of this problem with $(n_1,n_2)=(1617,0)$. One can also prove that it is possible to replace $4$ triangles by $3$ quadrilaterals and derive a solution with $(n_1,n_2)=(1613,3)$.

$\endgroup$
  • 2
    $\begingroup$ Your link does not work for me - it just says that the "file does not exist". $\endgroup$ – Gordon Royle Aug 29 '18 at 11:22
  • $\begingroup$ @GordonRoyle I am sorry, try now. $\endgroup$ – davidoff303 Aug 29 '18 at 12:33
  • 3
    $\begingroup$ @davidoff303 Conjecture 1 in the linked paper asserts that if $n$ is congruent to $3$ modulo $12$, then there is a graph with $n$ vertices such that every edge belongs to a unique triangle. The aim of the paper is to prove Conjecture 1 for $n<100$. I cannot see how the paper deals with the second condition, namely, that every non-edge belongs a unique quadrilateral. $\endgroup$ – Philipp Lampe Aug 29 '18 at 13:07
  • 3
    $\begingroup$ @davidoff303 I must concur with Philip, the paper only deals with the first part of the requirements. In addition to the triangle requirement , the graph Conway seeks must be 14-regular and every pair of non adjacent vertices must have exactly two common neighbours. If you build another such graph, you can test it with the Magma function IsDistanceRegular to see if you’re eligible to collect the $1k. $\endgroup$ – Gordon Royle Aug 29 '18 at 22:33
  • 4
    $\begingroup$ In $K_{99}$ every edge belongs to (i.e is an edge in) 97 triangles, the requirement is that each edge belongs to exactly 1 triangle. (This is what “unique triangle” means in this context - not 0 triangles, not 2 triangles, not more than 2). What Conway is actually asking is whether there is a $(99, 14, 1, 2)$ strongly regular graph, but he chose to phrase it less technically. $\endgroup$ – Gordon Royle Sep 1 '18 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.