# Construction of a graph

To construct a specific kind of undirected graph $G=(V,E)$, which $|V|=n>2$. For convenience, label the vertices with $v_1,v_2,\dots ,v_n\in V$, and $(v_i,v_j)\in E$ means there is a edge between vertices $v_i,v_j$.

And the graph has the following property:

• $(v_1,v_2)\in E$
• For $i\geq 3$, $(v_i,v_1)\in E\Rightarrow (v_i,v_2)\notin E$,and $(v_i,v_2)\in E\Rightarrow (v_i,v_1)\notin E$
• For $i\neq j,(v_i,v_j) \notin E \Rightarrow \exists v_{k_1},v_{k_2}(k_1\neq k_2)$ which $(v_{k_1},v_i),(v_{k_2},v_i),(v_{k_1},v_j),(v_{k_2},v_j)\in E$ and $\forall l\neq k_1,k_2, (v_l,v_i) \notin E$ or $(v_l,v_j)\notin E$

If $n$ is even, for instance, $n=12$, we can construct the graph like this:

But I couldn't construct one when $n$ is odd, for instance, when $n=5$, etc.

If $n\geq 3$ is an odd number, is it possible to construct a graph meet the above-mentioned property?

• I guess you mean "or" in the very last condition: $\forall\ l\ne k_1,k_2$ either $(v_l,v_i)\notin E$ or $(v_l,v_j)\notin E$. Or? :D – მამუკა ჯიბლაძე Mar 23 '16 at 6:25
• Also, are vertices $v$ with neither $(v,v_1)\in E$ nor $(v,v_2)\in E$ allowed? – მამუკა ჯიბლაძე Mar 23 '16 at 6:53
• @მამუკაჯიბლაძე Yes, it's allowed. – user79942 Mar 23 '16 at 7:32
• Is the following restatement correct? There are two adjacent vertices $v_1,v_2$ with no common neighbor; and any two nonadjacent vertices have exactly two common neighbors. – bof Mar 23 '16 at 9:44
• @bof Yes, correct. – user79942 Mar 23 '16 at 9:56

Notice that for every $n>3$ there should be a $C_4$ with no diagonal. For $n=5$, it is easy to see then that no such graphs exist.
For $n=7$, the Mycielski construction over $C_3$ fits. In other words, mark the vertices of an equilateral triangle with side length 2 and the midpoints of its sides; conect each two vertices at distance 1. Now add one more vertex which is connected to the three vertices of the initial triangle.