Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The question arose, while thinking about this one... –  draks ... Dec 28 '12 at 13:20
1  
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. –  Henning Makholm Dec 28 '12 at 14:12
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks for setteling the case. Would be glad if you could have a look at the linked one... –  draks ... Dec 31 '12 at 12:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.