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?

either$(v_l,v_i)\notin E$or$(v_l,v_j)\notin E$. Or? :D $\endgroup$ – მამუკა ჯიბლაძე Mar 23 '16 at 6:25