Prove or disprove a statement about $4$ regular graph with orientation

Question

Prove or disprove: there eixsts a $4$-regular graph $G$ of order 7 and an orientation $D$ of $G$ such that for every vertex $u$ of $D$, there eixts either a $u-v$ path of length 1 or a $u-v$ path of length 2 but now both for every vertex $v$ of $D$ with $v \not = u$

I tried so many graph but keep getting $u-v$ path of both length 1 and 2. I begin to think this statement is not true, but I can't find any counterexample either.

Answer 1

Assuming that what you want is (your formulation isn't all clear to me):

• between each pair of vertices there is at least one path of length at most two,
• path of length two implies no paths of length one,
• path of length one implies no paths of length two,

then no such example exists. To prove it:

• observe that the above conditions imply that any triangle has to be directed as a cycle,
• there are only two non-isomorphic 4-regular graphs with 7 vertices (see here).
• the two above bullets give you 3 cases that you can check for meeting the conditions.

I hope this helps $\ddot\smile$