Condition about regular graphs I am trying to do this graph theory exercise:

Let graph $G$ doesn't contain triangle and for each unconnected
  vertices of $G$ exists exactly two vertices that are neighbors of
  both. Show that graph is regular.

I can imagine only two cases of such graphs $K_2$ and $C_4$. Are there other such graphs? I need hint how to construct them.
 A: Once you know the graph is regular, it follows that your graph is strongly regular with parameters 
$$
\binom{k}{2}+1,\ k,\ 0,\ 2.
$$
In addition to the 4-cycle, there are two other examples - The Gewirtz graph on 56 vertices with $k=10$ and the one in the other example, known as the Clebsch graph. I think the details are all in Biggs's book "Finite Groups of Automorphisms".
A: Here is a proof of why the degrees have to be equal. Let $p$ be any node and $k = \deg(p)$ its degree. Assume $p$ is adjacent to nodes $v_1, v_2, \ldots, v_k$. We want to show that $\deg(v_i) = k$. 
Firstly, from the triangle condition, none of the $v_i$ are adjacent. Since they are not adjacent we can, for any pair of vertices $v_i, v_j$, find a vertex $w$ which is adjacent those two. Note that this $w$ is distinct for all pairs $v_i, v_j$, otherwise $w$ and $p$ would share more than two neighbours. 
Thus, with all these edges added we have that $\deg(v_i) = \deg(p)$ (you add in one edge for every other $v_j$). 
What we need to show now is that there is no way we can add more edges to any $v_i$. Assume $q$ is adjacent to $v_i$, and since it is not adjacent to $p$, to some $v_j$. But now $v_i, v_j$ have three neighbours: $w, p, q$. Contradiction. 
edit the following seems to be an example with degree 5.
Let $p, v_1, \ldots, v_5$ be as above, and $w_{ij}$ is adjacent to $v_i$ and $v_j$, for $i<j$. Add in the edges $[w_{ij}, w_{kl}]$ for $k>i, k\neq j, l\neq j$.
Every vertex has degree 5, no connected vertices share a neighbour, and seemingly the last condition is satisfied as well?
edit 2: it is a small exercise to see that it fails with $\deg(p) =3$ or $\deg(p) = 4$.
edit 3: as noted in the other answer, the example above is the Clebsch graph.
