Interpretation of combinatorial term for sub-graphs in strongly regular graphs

Question

In Brouwer's book "Strongly regular graphs" he mentions in the subsection on Quadratic counting that for any vertex induced subgraph $U$ of some strongly regular graph $L$ on $u$ vertices and $e$ edges one can derive certain quantities form the number of vertices $x_i$ outside of $U$ having exactly $i$ neighbors in $U$. He defines the degree sequence in $U$ as $(d_1,...,d_u)$. In particular, he gives for a strongly regular graph with parameters $(n,k,\lambda,\mu)$ the identity

$$\sum_{i}\binom{i}{2}x_i = \lambda e + \mu\left(\binom{u}{2}-e\right)-\sum_{i=1}^{u}\binom{d_1}{2}.$$

I would like to interpret this in term in a graph theoretical way. $\lambda e$ may be linked to the triangles in $L$ but I am not sure how, $\left(\binom{u}{2}-e\right)$ is the number of edges of the complement of $U$ in the complete graph on $u$ vertices. This is not much and I am completely stuck for the remaining terms/term combinations...

Answer 1

The left-hand side $\sum_i \binom i2 x_i$ is really the sum of $\binom{\deg_U(v)}{2}$ over all $v \notin U$: for every $v \notin U$, we count the number of pairs of neighbors in $U$ that $v$ has. Another way to think about this is as the number of paths $[u,v,w]$ where $u,w\in U$ and $v \notin U$; we consider $[u,v,w]$ and $[w,v,u]$ to be the same path.

On the right-hand side:

• $\lambda e$ counts the number of paths $[u,v,w]$ where $u,w \in U$ and $u$ and $w$ are adjacent. There are $e$ choices of adjacent pairs $u,w \in U$; for each of them, there are $\lambda$ ways to choose $v$.
• $\mu(\binom u2 - e)$ counts the number of paths $[u,v,w]$ where $u,w \in U$ and $u$ and $w$ are not adjacent. There are $\binom u2 - e$ choices of non-adjacent pairs $u,w \in U$; for each of them, there are $\mu$ ways to choose $v$.

Together, $\lambda e + \mu(\binom u2 - e)$ counts the number of paths $[u,v,w]$ where $u,w \in U$. This is missing the condition $v \notin U$.

To account for this, we subtract $\sum_{i=1}^u \binom{d_i}{2}$, which is exactly the number of paths $[u,v,w]$ where $u,v,w\in U$. That's because if $v$ has degree $d_i$, there are $\binom{d_i}{2}$ ways to choose $u,w \in U$ adjacent to $v$, which is exactly the same as choosing the path $[u,v,w]$ once $v$ has been chosen.