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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.