Every two vertices have two common neighbors I need to show that if $G$ is a graph such that every pair of vertices have exactly two neighbors in common, then $G$ is regular, and express the number of vertices in terms of its regularity.
Take any $v_1, v_2\in V(G)$ that are adjacent. Let $w_1\in N(v_1)$, then $w_1$ and $v_2$ share two common neighbors, one of which is $v_1$, the other one is $w_2$. 
Case 1: $w_1$ and $v_2$ are adjacent.
Case 2: If $w_1$ and $v_2$ are not adjacent, then $w_1$ is not a common vertex of $v_1$ and $v_2$, so there must be at least one vertex $w_3\notin\{w_1,w_2\}$ that is adjacent to both $v_1$ and $v_2$.
In all cases, every neighbor of $v_1$ induces an edge incident to $v_2$, so $deg(v_2)\geq deg(v_1)$. By symmetry $deg(v_1)\geq deg(v_2)$, and by connectedness, $G$ is regular.
But how is regularity related to the total number of vertices? 
 A: A graph $ G $ is strongly regular if it is $k$-regular and there exist integers $ \lambda, \mu $ such that for all pairs of distinct vertices $ u,v $ of $ G $ then


*

*if $ u $ and $ v $ are adjacent. there are exactly $ \lambda $ vertices adjacent to both $ u $ and $ v $;

*if $ u $ and $ v $ are nonadjacent. there are exactly $ \mu $ vertices adjacent to both $ u $ and $ v $.


We now derive a relation between the parameters of such a graph.
For such a graph of order $ n $ fix a vertex $ v $. Let $ N $ be the set of neighbours of $ v $, let $ M $ be the set $ V(G) \setminus (N \cup \{v\}) $. Then $ |N| = k, |M| = n-k-1 $.
Each vertex of $ N $ has exactly $ \lambda $ common neighbours with $ v $ and so $ \lambda + 1 $ neighbours lying in $ N $; hence vertices of $ N $ each have $ k - \lambda - 1 $ edges into $ M $ and there are $ |N|(k - \lambda - 1) = k(k - \lambda - 1) $ edges between $ N $ and $ M $.
Each vertex of $ M $ has exactly $ \mu $ common neighbours with $ v $ and so exactly $ \mu $ neighbours in $ N $. Hence the number of edges between $ N $ and $ M $ is $ |M| \mu = (n - k -1) \mu $.
We have therefore shown that for a graph $ G $ of order $ n $ that is $ k$-regular and such that adjacent vertices have $ \lambda $ common neighbours and nonadjacent vertices have $ \mu $ common neighbours, $ k(k - \lambda - 1) = (n - k -1) \mu $. This result is well-known, e.g. it appears on the Wikipedia page.
For the special case in the question, $ \lambda = \mu = 2 $ and so $ n = \frac{1}{2}(k^2 - k + 2) $.
