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

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.

Tags:

Graph Theory