# A conjecture about strongly regular graphs

Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$

So far I have not been able to prove it, though it seems like an easy statement. Have you seen something like this?

EDIT:

Now that the original claim is proved, we can ask: what is the best possible constant $C$ so that $\lambda-\mu \leq \frac{k}{C}$?

• $G$ should not be complete graph, yes? – Fedor Petrov Aug 20 '14 at 11:01
• @FedorPetrov Yes, let's exclude it. – Felix Goldberg Aug 20 '14 at 11:07

I have found a proof now. There is an old result, due originally to Taylor & Levingston, which says that for a strongly regular $G \neq K_{v}$:

$$k \geq 2\lambda+3-\mu.$$

It can be found on page 7 of the BCN book and in fact holds for a more general class (the so-called amply regular graphs) as pointed out by Neumaier.

Now we can prove the claim in the question by considering two cases:

(I) $\lambda \leq \frac{k}{2}$. Then $\lambda-\mu \leq \lambda \leq \frac{k}{2}$.

(II) $\lambda>\frac{k}{2}$. Then $\lambda-\mu \leq (k-\lambda)-3<k-\lambda<\frac{k}{2}$.

QED

• Or without cases $k\geq 2\lambda+3-\nu>2\lambda-2\nu$. – Fedor Petrov Aug 21 '14 at 14:43