# minimum number of vertices for a specific graph

Today I saw this problem:

Find the smallest $n\ge 5$ such that there exists a simple graph on $n$ vertices such that any two adjacent vertices have no common neighbours, and any two non-adjacent vertices have exactly $2$ common neighbours.

I derived the identity $\sum_{i=1}^{n} \dbinom{d_{v_i}+1}{2}=\dbinom{n}{2}$ and using this, I could prove that $n\ge 9$, but I couldn't go any further. Any Ideas?

-
what's the advantage of doing that? – Goodarz Mehr Feb 26 '12 at 18:45
The Clebsch Graph has this property, and has 16 vertices, so that is an upper bound for $n$... – jp26 Feb 27 '12 at 1:46
thats really a great example!!! but how to prove there isn't such a graph having smaller number of vertices? – Goodarz Mehr Feb 27 '12 at 4:34
If this seems a bit too complicated, look up strongly regular graphs. As the answer shows, your condition implies the graph is regular. And, if a graph is regular and satisfies the conditions you gave, it is called strongly regular. There is a lot of theory behind strongly regular graphs. Once you know that, this problem is probably pretty easy. – Graphth Feb 27 '12 at 16:07

Start with an arbitrary vertex $z$. Let $D$ be the set of its neighbors and let $N$ be the set of vertices other than $z$ who are adjacent to some vertex in $D$. Let $d$ be the size of $D$: this is the degree of $z$. No two vertices of $D$ are adjacent to each other (since every such pair has a common neighbor, namely $z$).

So every such pair must also have just one other common neighbor other than $z$, and that common neighbor is in $N$. We obtain a well-defined, injective mapping from "pairs of vertices in $D$" into "vertices in $N$". The reason this map is injective is that different pairs must find different common neighbors in $N$: if two pairs shared the same common neighbor $v \in N$, then $z$ and $v$ would have more than 2 mutual friends.

In fact, the same argument shows that our mapping is also onto: every vertex of $N$ is such a common neighbor for a certain pair of vertices in $D$, since it must have two mutual friends with $z$. Therefore our mapping is one-to-one and onto, and $N = \binom{d}{2}$.

Now a key observation is that $\{z\} \cup D \cup N$ are all the vertices of the graph, since any vertex outside of this union cannot have any mutual neighbor with $z$ which is forbidden. So the number of vertices of the graph is $n=1+d+\binom{d}{2}$, and since $z$ was completely arbitrary we find that the graph is regular: all vertices must have the same degree $d$, the one which makes $n=1+d+\binom{d}{2}$ true.

Let us label the elements of $D$ with the integers $\{1,2,\ldots,d\}$. The elements of $N$ are naturally labeled by (unordered) pairs $\{i, j\}$ with $1 \leq i \neq j \leq d$, and the vertex (corresponding to) $\{i,j\}$ is connected to two vertices of $D$, namely $i$ and $j$. Since $\{i,j\}$ has degree $d$, it must have $d-2$ additional neighbors in $N$ itself.

Consider two vertices of $N$, say $\{i,j\}$ and $\{i,k\}$, which share a friend $i \in D$. Having a mutual friend implies that they themselves must not be adjacent. Since for every pair of number $\{i,j\}$ we can find $2d-4$ other pairs that intersect it this way, we find that each $\{i,j\} \in N$ has $2d-4$ non-neighbors in $N$.

It follows that $N$ contains at least $1+(d-2)+(2d-4)$ vertices, and since $N=\binom{d}{2}$ we must have $3d-5 \leq \binom{d}{2}$. This fails for $d=3,4$ (the case $d=2$ obviously corresponds to the case where the whole graph is just a 4-cycle, which satisfies all the requirements except that it has $n<5$ vertices). It does work for $d=5$, so this is our candidate for smallest answer: a 5-regular graph with 16 vertices. We assume $d=5$ from now on.

So consider again an arbitrary member $\{i,j\}$ of $N$, with $i,j$ now in the range $\{1,\ldots,5\}$. It has 6 non-friends in $N$ (all pairs which include either $i$ or $j$) and 3 friends, which must therefore be exactly all the pairs $\{k,l\}$ that are disjoint from $\{i,j\}$. You might recognize this as one of the descriptions of the Petersen graph: we've concluded that the graph induced by $N$ is Petersen.

In fact, we now have a complete description of the whole graph: it consists of 3 sets of vertices, $\{z\}$, $D=\{1,\ldots,5\}$ and $N=$ the set of pairs of elements of $D$. Every vertex $\{i,j\}$ in $N$ is connected to $i$ and to $j$ in $D$ as well as to the vertices $\{k,l\}$ in $N$ that are disjoint from it.

It's easy to check that this construction satisfies all the requirements of the problem, and as pointed out in the comments, it is none other than the Clebsch graph.

-
thanks a lot. really really beautiful!!!! – Goodarz Mehr Feb 27 '12 at 16:57