Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 1

up vote 10 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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