proof regularity of graph I have the following question:
Suppose Γ is a non-complete graph, with every pair of joined vertices having exactly one common neighbor and every pair of non-joined vertices having exactly 2 common neighbors. My professor proved in class that such a graph is regular by proving that any two non-joined vertices have the same number of neighbors. My question is: do we not also need to prove any two joined vertices have the same number of neighbors and that these two numbers (for joined and non joined) are the same? 
Thanks in advance.
 A: Let $\Gamma_2$ be the graph with the same vertex set as $\Gamma$, but with two vertices in $\Gamma_2$ adjacent if and only if they are at distance two in $\Gamma$. Your professor's argument is valid provided $\Gamma_2$ is connected. But if $\Gamma_2$ is not connected then $\Gamma$ must be bipartite and, since it contains triangles, it is not bipartite.
To see my first claim, if $a$ and $b$ are vertices at distance two and $c$ is at distance two from $b$, then $a$ and $c$ must have the same valency, and so it follows that vertices in the same component of $\Gamma_2$ have the same valency in $\Gamma$. For the second claim, the key is that any two vertices that lie on an
odd cycle must have the same valency.
A: If any two non-joined vertices have the same number of neighbors, take a,b to be non joined vertices of Γ. Then there is a neighbor of b that is not connected to a: Since a and b have precisely two common neighbors and b must have exactly one common neighbor with each of them (call them c1 and c2). note: a cant be connected to either c1 or c2 cause then it has 3 common neighbors with b. So then a and c1,c2 have the same valency. So then b and c1,c2 have the same valency. But b and c1,c2 are connected. 
