Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Show that a strongly regular graph with $28$ verticies each with valency $9$ such that adjacent pairs are not joined and non-adjacent pairs share exactly $4$ vertices does not exist.

A really bad proof is the following: If such an object existed, some clever spark would have found it, and despite an extensive search I have not found it in the literature. I have a toe curling argument involving 4 subsets of a 9 set and then some, that doesn't even convince me!

Is there a reasonably simple counting arguement that shows the non-existence of this? Failing that a reference to a computer search that shows it?

As usual my thanks in advance to all who offer a response. HK

share|cite|improve this question
"adjacent pairs are not joined"? What does that mean? If two vertices are adjacent, that means they are joined, no? – Gerry Myerson Jun 6 '12 at 9:10
Nice one Jerry! This explains why no one responded to this queston. I meant to say that if two verticies are adjacent then there are no other verticies that are mutually adjacent to these two veticies. (This is the zero as the third parameter in the question, google strongly regular graphs!) This problem is still my drop off to sleep thoughts. – Herman Jun 6 '12 at 16:14

A useful resource for strongly regular graphs and graph spectra in general is prof. dr. Andries E. Brouwer's website (see e.g. his tables of parameters and existence/uniqueness) and his lecture notes on spectra of graphs. On page 117-118 of the preprint you will find conditions on the parameters that have to be satisfied by any set of parameters, which are not satisfied by the parameter set $(28,9,0,4)$. This example is actually explicitly mentioned there, not satisfying the bound $v \leq g (g+3) / 2$ (in this case $v = 28$ and $g = 6$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.