Proof that if $G$ graph doesn't contain triangle, and every $2$ non-neighbour vertexes have only $2$ common neighbour vertexes, then $G$ is regular ($G$ s each vertex's degree is equal to the same number).
I understood this. if it doesn't contain any triangle, it means that $$\left|E(g)\right| \le \left[\frac{|V(g)|^2}{4}\right]$$ But it doesn't help as I see. Any Ideas?
Suppose two vertices $a$ and $b$ are neighbours. I claim $a$ and $b$ have the same degree. It is enough to show that $a$ has at least as many neighbours as $b$. Say $a$ has $k$ neighbours $c_1, \ldots, c_{k}$ besides $b$. Since there are no triangles, these are not neighbours of $b$. So $c_i$ and $b$ have two common neighbours: one is $a$, and let the other be $d_i$. These must be distinct, as $d_i$ and $a$ (which can't be neighbours because there are no triangles) have only two common neighbours $b$ and $c_i$. Thus $b$ has (at least) $k$ neighbours besides $a$.
Now suppose vertices $a$ and $b$ are not neighbours. Again, I claim $b$ has at least as many neighbours as $a$. They have two common neighbours $c$ and $d$, which are not neighbours since there are no triangles. Suppose $a$ has $k$ other neighbours $e_1, \ldots, e_k$.
For any $j$, $e_j$ can't be a neighbour of any of $c$, $d$, or $b$. $e_j$ and $c$ have $a$ as common neighbour, so they must have one other common neighbour $f_j$, which can't be a neighbour of $a$, $b$ or $c$. Moreover the $f_j$ for different $j$ must be distinct: if $f_i = f_j$, $a$ and $f_i$ would have at least three common neighbours $e_i$, $e_j$ and $c$. $f_j$ and $b$ are not neighbours and have $d$ as a common neighbour, so they must have another common neighbour $g_j$. Again, the $g_j$ must be distinct. Thus $b$ has at least $k$ other neighbours $g_1, \ldots, g_k$.