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: enter image description here

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?

  • $\begingroup$ 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 $\endgroup$ Commented Mar 23, 2016 at 6:25
  • 1
    $\begingroup$ Also, are vertices $v$ with neither $(v,v_1)\in E$ nor $(v,v_2)\in E$ allowed? $\endgroup$ Commented Mar 23, 2016 at 6:53
  • 1
    $\begingroup$ @მამუკაჯიბლაძე Yes, it's allowed. $\endgroup$
    – user79942
    Commented Mar 23, 2016 at 7:32
  • 5
    $\begingroup$ 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. $\endgroup$
    – bof
    Commented Mar 23, 2016 at 9:44
  • 1
    $\begingroup$ @bof Yes, correct. $\endgroup$
    – user79942
    Commented Mar 23, 2016 at 9:56

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.