Let $G$ be a $2$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient the edges of $G$ such that for each vertex $v$, there are no three consecutive edges (in the clockwise direction) such that all of them are oriented towards $v$ or all of them are oriented outwards from $v$. Does such orientation always exist?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Such an orientation always exists, here is a proof.
Take your 2-edge-connected graph $G$, and consider its dual graph $D$. $D$ has a proper 4-coloring in which each face of $D$ contains at most 3 different colors (add a vertex inside each face of $D$, connect it to all the vertices of the face, and apply the four color theorem to the resulting graph). Now, orient each edge of $D$ from the smaller color to the larger color. Note that there is no facial directed path on more that 2 edges in $D$ (otherwise, this would be a path with all 4 colors). Now, transfer the orientation of the edges of $D$ to the edges of $G$ in the natural way, and you get the desired result.
(in the first version of this post, the proof only gave that in 4-edge-connected plane graphs, you can find the desired orientation, and in 2-edge-connected plane graphs, you can find an orientation in which no four consecutive edges around a vertex have the same orientation)
-
$\begingroup$ I slightly modified the proof. Now you have the property that you need. $\endgroup$ Oct 11, 2018 at 12:38