Talk:Strongly regular graph

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

Potentially inaccurate statement in examples

I am not an expert on graph theory, so I hesitate to update the article itself. However, I believe the categorical statement:

The strongly regular graphs with λ=0 are triangle free. The seven listed above are the only known ones.

is incorrect. If I understand the subject correctly, every complete bipartite graph on an even number of vertexes is also strongly regular, with signature srg(2 k, k, 0, k), and bipartite graphs with signature srg(2 k, k, 0, p), with p < k, are easily constructed. — Preceding unsigned comment added by 98.26.29.11 (talk) 12:45, 22 May 2012 (UTC)[reply]

I need to retract the construction remark - the only strongly regular bipartite graphs are complete.

Proof of $(v-k-1)\mu =k(k-\lambda -1)$

I was unable to find a reference to cite for this formula. However, the proof is pretty simple:

Consider a strongly regular graph G with parameters (v,k,λ,μ) and vertex set V. Let n(x) be the set of vertexes in V that are adjacent to the vertex x in G, and let p(x) be the set of vertexes in V that are neither the vertex x nor in n(x). Then, consider a particular vertex q. Every vertex t in n(q) forms an edge with λ vertexes in n(q). Further, t forms an edge with q. This leaves k-λ-1 edges that have one vertex in n(q) and one vertex in p(q). Taken over all vertexes adjacent to q, this gives k (k-λ-1).

Next, consider the set of vertexes p(q). For every vertex t in p(q), q forms an edge with μ vertexes in n(t). By the partitioning of V, there are v-k-1 vertexes in p(q). Thus, the vertexes in p(q) form (v-k-1) μ edges with the vertexes in n(q). But this is the same set of edges that were counted in the preceding paragraph. Hence, (v-k-1) μ = k (k-λ-1).

Potentially inaccurate statement in examples

Proof of ( v − k − 1 ) μ = k ( k − λ − 1 ) {\displaystyle (v-k-1)\mu =k(k-\lambda -1)}

Proof of $(v-k-1)\mu =k(k-\lambda -1)$