2
$\begingroup$

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?

  • 0
    @AustinMohr: As you wish.2012-11-24
  • 0
    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.2012-11-24
  • 0
    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](http://larmor.nuigalway.ie/~detinko/Matan.pdf).2012-11-24

1 Answers 1