# The existence and uniqueness of a strongly regular graph of order 100 and degree 22.

I am working on an exercise question asking me to "discuss the possibilities of a triangle-free strongly regular graph of order 100 and degree $d$".

Let $b$ be the parameter of the number of common neighbors of 2 non-adjacent vertices. Then pick any vertex $u$, it has $d-1$ neighbors, which must be pairwise non-adjacent for the graph to be triangle-free. Each of the neighbors of $u$ must therefore be adjacent to $d-1$ non-neighbors of $u$. So $d(d-1)$ edges run from neighbors of $u$ to non-neighbors of $u$. On the other hand, each non-neighbor of $u$ must connect to $b$ neighbors of $u$. So there are $b(99-d)$ edges running from non-neighbors of $u$ to neighbors of $u$.

So I get $d(d-1)=(99-d)b$. Having messed about this equation and double checked using all the theorems I know, I have only the following possibilities:

1. The graph is empty
2. The graph is 1-factor
3. The graph is $K_{50,50}$
4. The graph has $d=22$ and $b=6$.

I know that the first 3 possibilities are valid. I want to eliminate or prove the existence or even the uniqueness of the last possibility but have no idea how. I looked up a database and in fact the last possibility uniquely exists.

Can someone prove the existence and uniqueness of possibility 4?

-
@AustinMohr: As you wish. – hardmath Nov 24 '12 at 19:15
You should ask your professor what is expected of you. The best any of us can do is speculate what s/he expects from this question. A better question for this site is to prove or disprove the existence of item 4. – Austin Mohr Nov 24 '12 at 19:36
Some interesting history, supplementing what you found in that "database" link, is recounted in these slides from a talk last year by Matan Ziv-Av. – hardmath Nov 24 '12 at 20:06

It's hard to know what specifically is expected from the class on this exercise. You've gotten pretty far with the equation $d(d-1)=(99-d)b$. I'd guess tested for what values $b \lt d$ and perhaps applied some of the algebraic conditions counting eigenvalue multiplicity to isolate $d = 22$ and $b = 6$ as an interesting possibility.