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.

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.