# Is there a graph with 99 vertices in which every edge belong to a unique triangle and every nonedge to a unique quadrilateral?

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?

-
To guarantee the "every" and "unique" conditions is not easy. –  Rupei Xu Apr 6 at 7:40
You of course have $\binom{99}{2} = 3t + 4q$ where $t$ is the number of triangles, and $q$ is the number of quadrilaterials, so there are some restrictions, if such a solution exists. –  Per Alexandersson Apr 6 at 8:49
Professor John Conway (Princeton University) would like to offer $1,000 for this problem to the one who first solves it. – Rupei Xu Apr 9 at 6:21 ## 1 Answer 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.

-
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?) –  The Masked Avenger Apr 6 at 15:46
@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. –  Brendan McKay Apr 6 at 16:00
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? –  The Masked Avenger Apr 6 at 16:10
I see. I thought the edge was part of the (blue) quadrilateral. Certainly your view is more intriguing. Thanks. –  The Masked Avenger Apr 6 at 16:12
Thank you for your helpful analysis and references. Life is so beautiful with a nice Professor like you! –  Rupei Xu Apr 9 at 6:20