Going with/against the orientation alternates along the Hamilton cycle?











up vote
6
down vote

favorite
1












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.










share|cite|improve this question
























  • Might clockwise and counter clockwise be better terms than left and right?
    – abnry
    Oct 9 '16 at 2:08










  • $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?.
    – arthur
    Oct 9 '16 at 15:15












  • @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...
    – draks ...
    Oct 10 '16 at 5:55















up vote
6
down vote

favorite
1












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.










share|cite|improve this question
























  • Might clockwise and counter clockwise be better terms than left and right?
    – abnry
    Oct 9 '16 at 2:08










  • $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?.
    – arthur
    Oct 9 '16 at 15:15












  • @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...
    – draks ...
    Oct 10 '16 at 5:55













up vote
6
down vote

favorite
1









up vote
6
down vote

favorite
1






1





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.










share|cite|improve this question















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.







graph-theory algebraic-graph-theory planar-graph bipartite-graph






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 4 hours ago

























asked Sep 23 '16 at 13:02









draks ...

11.6k643125




11.6k643125












  • Might clockwise and counter clockwise be better terms than left and right?
    – abnry
    Oct 9 '16 at 2:08










  • $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?.
    – arthur
    Oct 9 '16 at 15:15












  • @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...
    – draks ...
    Oct 10 '16 at 5:55


















  • Might clockwise and counter clockwise be better terms than left and right?
    – abnry
    Oct 9 '16 at 2:08










  • $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?.
    – arthur
    Oct 9 '16 at 15:15












  • @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...
    – draks ...
    Oct 10 '16 at 5:55
















Might clockwise and counter clockwise be better terms than left and right?
– abnry
Oct 9 '16 at 2:08




Might clockwise and counter clockwise be better terms than left and right?
– abnry
Oct 9 '16 at 2:08












$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?.
– arthur
Oct 9 '16 at 15:15






$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?.
– arthur
Oct 9 '16 at 15:15














@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...
– draks ...
Oct 10 '16 at 5:55




@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...
– draks ...
Oct 10 '16 at 5:55










2 Answers
2






active

oldest

votes

















up vote
2
down vote



accepted
+500










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.






share|cite|improve this answer





















  • I think this is perfectly right...
    – draks ...
    Oct 10 '16 at 5:59


















up vote
0
down vote













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$.






share|cite|improve this answer























    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














     

    draft saved


    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1938392%2fgoing-with-against-the-orientation-alternates-along-the-hamilton-cycle%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    2
    down vote



    accepted
    +500










    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.






    share|cite|improve this answer





















    • I think this is perfectly right...
      – draks ...
      Oct 10 '16 at 5:59















    up vote
    2
    down vote



    accepted
    +500










    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.






    share|cite|improve this answer





















    • I think this is perfectly right...
      – draks ...
      Oct 10 '16 at 5:59













    up vote
    2
    down vote



    accepted
    +500







    up vote
    2
    down vote



    accepted
    +500




    +500




    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.






    share|cite|improve this answer












    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.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Oct 9 '16 at 0:28









    Anatoly

    11.8k21437




    11.8k21437












    • I think this is perfectly right...
      – draks ...
      Oct 10 '16 at 5:59


















    • I think this is perfectly right...
      – draks ...
      Oct 10 '16 at 5:59
















    I think this is perfectly right...
    – draks ...
    Oct 10 '16 at 5:59




    I think this is perfectly right...
    – draks ...
    Oct 10 '16 at 5:59










    up vote
    0
    down vote













    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$.






    share|cite|improve this answer



























      up vote
      0
      down vote













      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$.






      share|cite|improve this answer

























        up vote
        0
        down vote










        up vote
        0
        down vote









        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$.






        share|cite|improve this answer














        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$.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Oct 9 '16 at 19:55

























        answered Oct 7 '16 at 19:47









        draks ...

        11.6k643125




        11.6k643125






























             

            draft saved


            draft discarded



















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1938392%2fgoing-with-against-the-orientation-alternates-along-the-hamilton-cycle%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Quarter-circle Tiles

            build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

            Mont Emei