6
$\begingroup$

Below you see an example of a bicubic graph consisting of faces with degree $4$ and $6$, which makes up the set of graphs of my interest and is a subset of the so called Barnette graphs.

$\hskip1.7in$enter image description here

Since the graph is planar it has a 4-coloring of the faces and therefore a 3-coloring of the edges. If you color the edges along the Hamilton Cylce (HC) given by the increasing labels with the colors 1 and 2 (color 0 is left for the non HC edges).

Using this 3-coloring you can assign an orientation to every vertex. Just look at the graph and check how the colors 0,1 and 2 result in an orientation. For the example above you get: $$ LRLL|RLRR|LRLL|RLRR|LLRR $$

E.g. at vertex 2, the edge (1,2) has color 1, edge (2,3) has color 2 and edge (2,9) has color 0. So the vertex has a right orientation, i.e. $R$.

The first observation from the examples we have so far (the cube and another 12 vertex graph) is that the orientations occur balanced, i.e. you get the same number of left and right oriented vertices. (Proven below...)

But if you now go along the HC, i.e. you start from 1 and go to 2 you have to turn left, which is against the orientation of the vertex, which is right. I write $0$ for wrong and $1$ for correct orientation. What you now get is, at least stunning to me: $$ 01010101010101010101 $$ How to prove that?

I also checked an alternative HC for the graph given above and some simpler graphs with the same result.

$\endgroup$
  • $\begingroup$ Might clockwise and counter clockwise be better terms than left and right? $\endgroup$ – abnry Oct 9 '16 at 2:08
  • $\begingroup$ $2(R) \to 3(L)$ and $3(L) \to 4(L)$ are identical left turns into $(L)$ oriented nodes producing a $11$ in the pattern. I'm taking the direction of a turn to mean you walk down the edge approaching the node and are facing along that line. A left or right turn is relative to that axis and orientation?. $\endgroup$ – arthur Oct 9 '16 at 15:15
  • $\begingroup$ @arthur relative to the local orientation given by the vertex orientation. $2(R)\to 3(L)$ and $3(L)\to 4(L)$ both turn left, but for $2$ this is wrong and for $3$ it's correct... $\endgroup$ – draks ... Oct 10 '16 at 5:55
2
+500
$\begingroup$

In this answer, I assume that "correct" occurs when the HC path either arrives to a right-oriented node and turns right, or arrives to a left-oriented node and turns left. In other words, I assume that the behaviour of the HC at a given node is compared to the orienting of the same node. I specify this because the last example given in the OP could suggest that the behaviour of the HC at a given node is compared to the orienting of the successive node (however, I checked this alternative possibility and noted that it generates no regular alternance). In addition, I assume that "right-oriented" refers to a node where the $0/1/2$ color sequence of the relative edges is clockwise, and that "left-oriented" refers to a node where this sequence is counterclockwise.

Let us begin by considering the $i^{th} $ node of the HC, calling it $N_i $. Let us consider firstly the case in which the HC edge arriving to it from the preceding node $N_{i-1}$ has colour $1$ (and consequently the HC edge starting from $N_i $ towards $N_{i+1}$ has colour $2$).

Under these conditions, we can distinguish the following two subcases. If $N_{i}$ is a right-oriented node, then the HC turns on the left in $N_{i}$ (in fact, because a right-oriented node must have the $0/1/2$ colour edges in a clockwise order, it is necessary that the $0$-colour, non-HC edge goes on the right). On the other hand, if $N_{i}$ is a left-oriented node, then the HC turns on the right in $N_{i}$ (a left-oriented node must have the $0/1/2$ colour edges in a counterclockwise order, so that the $0$-colour, non-HC edge goes on the left). As a result, in both subcases the HC turns wrongly. This means that, along the HC, in any node that terminates a colour $1$ edge (and that starts a colour $2$ edge) the behaviour of the HC is wrong.

Now let us consider the inverse case, in which the HC edge arriving to $N_i $ has colour $2$, and that starting from $N_i $ has colour $1$. By considerations similar and specular to those above, we get that if $N_{i}$ is a right-oriented node, then the HC turns right in $N_{i}$, whereas if $N_{i}$ is a left-oriented node, then the HC turns left in $N_{i}$. As a result, in both subcases the HC turns correctly. This means that, along the HC, in any node that terminates a colour $2$ edge (and that begins a colour $1$ edge) the behaviour of the HC is correct.

Therefore, because the HC is by definition composed by edges with a regular alternance of colour $1$ and colour $2$, we get that its behaviour must necessarily follow a correct/wrong alternance as well.

$\endgroup$
  • $\begingroup$ I think this is perfectly right... $\endgroup$ – draks ... Oct 10 '16 at 5:59
0
$\begingroup$

I can prove the first observation:

Replace every vertex with a triangle. The resulting graph is not bipartite anymore, but that's just a remark. Let's assume that the original graph had hamiltonian cycle (that Barnette's conjecture), then our triangle version will have a HC.

Then Grinberg's Theorem assures that: $$ 0=(f_3-g_3)+\sum_{k>3}(k-2)(f_k-g_k)\tag{1} $$

Denote by $f_k$ and $g_k$ the number of $k$-gonal faces of the embedding that are inside and outside of HC.

Interpret triangles inside the HC as left (L), outside ones as right (R). That shows that their number of occurences is equal.

Since $f_3+g_3=n$, it is proven that $f_3=g_3=\frac n2$ and therefore $\#L=\#R=\frac n2$.

$\endgroup$

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.