Consider a simple undirected graph in which every pair of distinct non-adjacent vertices have precisely μ common neighbors, and every pair of adjacent vertices have precisely λ common neighbors. Examples of such graphs are friendship graphs (with μ = 1, λ = 1) and Moore graphs of diameter 2 (with μ = 1, λ = 0). Certain additional conditions force such a graph to be strongly regular, in the sense of all its nodes furthermore having the same degree. One such condition is μ = 0. Another such condition is that μ = 1 while no node is adjacent to all others. At any rate, any two non-adjacent nodes in such a graph have the same number of neighbors. We can see all this as follows:

When μ = 0, the condition that every pair of distinct non-adjacent vertices have precisely zero common neighbors is equivalently the condition that the "x is adjacent to or equal to y" relation is transitive. This relation is also automatically reflexive and symmetric, so it becomes an equivalence relation. The condition that every pair of adjacent vertices have precisely λ common neighbors is then the assertion that the equivalence classes each contain precisely λ + 2 elements. That is to say, the graph is a union of disjoint complete graphs on λ + 2 nodes each. This is clearly strongly regular. (Note also that this covers the degenerate cases of a graph with no adjacent nodes or with no non-adjacent nodes, for which μ or λ are not unambiguously determined). From hereon out, we thus presume μ > 0.

Let A and B be non-adjacent nodes, and consider paths from A to B through two intermediate nodes. The μ neighbors of A which are also neighbors of B have λ ways of being the first intermediate node, and the remaining neighbors of A which are not neighbors of B have μ ways of being the first intermediate node. Thus, the number of neighbors of A is equal to the number of such paths divided by μ and then added to μ - λ. The same is symmetrically true for neighbors of B, and thus A and B have the same number of neighbors.

Next, we note that there are two possibilities for such a graph. Either there is or there is not some node which is adjacent to all others.

If there is such a node adjacent to all others, then the conditions on the subgraph with this node removed are that any two distinct non-adjacent nodes have precisely μ - 1 common neighbors, any two adjacent nodes have λ - 1 common neighbors, and any node at all has λ neighbors. Given either of the last two conditions, the other of the last two conditions is equivalent to the transitivity of the previously discussed "x is adjacent or equal to y" relation on the subgraph. Note that the first condition is also equivalent to this transitivity if μ = 1, while the first condition is incompatible with this transitivity for any other value of μ (except in the degenerate sense that μ is not unambiguously determined if the original graph has no non-adjacent nodes). Thus, the combination of all three conditions is equivalent to the assertion that μ = 1 and the subgraph is a union of disjoint complete graphs on λ + 1 nodes each. In other words, the original graph is the gluing together of complete graphs on λ + 2 nodes each, identifying together one node from each such graph (again, we note that this works precisely when μ = 1. For λ = 0, this is a hub and spokes. For λ = 1, this is a windmill graph).

Finally, suppose there is no node adjacent to all others. If μ = 1, then the equivalence relation generated by non-adjacency relates any two nodes (indeed, the following argument applies even if there is some node adjacent to all others, so long as the two nodes in question are not of that form). Indeed, any two nodes are related by a "non-adjacency-path" (that is, a sequence of nodes each non-adjacent to the next) with at most two intermediate nodes. To see this, let A and B be two nodes. There may be a "non-adjacency-path" from A to B through less than two intermediate nodes, in which case we are done. If not, then A and B are distinct, A is adjacent to B, and every node non-adjacent to one of A or B is adjacent to the other. Thus, letting A' be some node non-adjacent to A and B' be some node non-adjacent to B, we have a path (a normal path of adjacent nodes) from A' to B to A to B', with all four nodes distinct. If A' and B' were themselves adjacent, then A and B would have two common neighbors, which is forbidden. Thus, A is non-adjacent to A' which is non-adjacent to B' which is non-adjacent to B.

Thus for μ = 1, for any value of λ, if there is no node adjacent to all others, the graph is strongly regular.

At this point, we can apply the theory of strongly regular graphs (in particular, investigation of eigenvalue multiplicity constraints) to further classify the possibilities, showing that there are no strongly regular graphs for μ = 1, λ = 1 (the "Friendship Graph Theorem"), and very limited possibilities for μ = 0, λ = 1 (the classification of Moore graphs of diameter 2).

TODO: Describe the eigenvalue multiplicity properties of strongly regular graphs.

TODO: Describe the uniqueness arguments for the Petersen graph and the Hoffman-Singleton graph (that is, they are the unique Moore graphs of diameter 2 of their sizes).