Strongly regular graph: Difference between revisions

Revision as of 22:28, 8 July 2023

Revision as of 22:30, 8 July 2023

Line 99:

The above relation is derived through a counting argument as follows:

# Imagine the vertices of the graph to lie in three levels. Pick any vertex as the root, in Level 0. Then its ''k'' neighbors lie in Level 1, and all other vertices lie in Level 2.

# Vertices in Level 1 are directly connected to the root, hence they must have λ other neighbors in common with the root, and these common neighbors must also be in Level 1. Since each vertex has degree ''k'', there are <math>k - \lambda - 1</math> edges remaining for each Level 1 node to connect to nodesvertices in Level 2. Therefore, there are <math>k (k - \lambda - 1)</math> edges between Level 1 and Level 2.

# Vertices in Level 2 are not directly connected to the root, hence they must have μ common neighbors with the root, and these common neighbors must all be in Level 1. There are <math>(v - k - 1)</math> vertices in Level 2, and each is connected to μ nodesvertices in Level 1. Therefore the number of edges between Level 1 and Level 2 is <math>(v - k - 1)\mu</math>.

# Equating the two expressions for the edges between Level 1 and Level 2, the relation follows.