1
$\begingroup$

Assume a planar graph with a Hamilton cycle (depicted in green).

$\hskip2in$enter image description here

There are two possiblities for the displayed vertices to show up al0ng the Hamilton cycle:

  1. $\dots ef\dots xy\dots$
  2. $\dots ef\dots yx\dots$

What does it mean for the square $F$, if it's $xy$ or $yx$? Does this mean that it's inside or outside the Hamilton cycle? Does Grinberg's Theorem play a role here?

$\endgroup$
2
  • $\begingroup$ The question arose, while thinking about this one... $\endgroup$
    – draks ...
    Dec 28, 2012 at 13:20
  • 1
    $\begingroup$ Intuitively ..ef..xy.. should be impossible, because F cannot both be in the component of the plane that lies to the left of the cycle and the component that lies to the right. $\endgroup$
    – hmakholm left over Monica
    Dec 28, 2012 at 14:12

1 Answer 1

Reset to default
1
$\begingroup$

Expanding the comment-answer by Henning Makholm: case 1 is impossible. A Hamilton cycle in a planar graph is a simple closed curve $\Gamma$ (a Jordan curve). By the Jordan curve theorem $\Gamma$ divides the plane into two regions: bounded $B$ and unbounded $U$. The region $B$ is homeomorphic to a disk by the Schoenflies theorem. The orientation of $B$ induces positive orientation of its boundary $\Gamma$, formalizing the intuitive notion of "$B$ stays to the left of its boundary". Since the square $F$ is either in $B$ or in the complement of $B$, case 1 is inconsistent with such orientation.

$\endgroup$
1
  • $\begingroup$ Thanks for setteling the case. Would be glad if you could have a look at the linked one... $\endgroup$
    – draks ...
    Dec 31, 2012 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .