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:
- The graph is empty
- The graph is 1-factor
- The graph is $K_{50,50}$
- 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?