<p>Yes, it is still <span class="math-container">$NP$</span> complete. This is because of:</p>

<p>Claim: All Hamiltonian cycles on maximal planar graphs are balanced.</p>

<p>Proof: This is a special case of Grinberg's theorem: <a href="https://en.wikipedia.org/wiki/Grinberg%27s_theorem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Grinberg%27s_theorem</a></p>

CC BY-SA 4.0
2018-12-06T18:06:05.003Z
2019-04-06T00:37:52.920Z
2019-04-06T00:37:52.920Z
Elle Najt
<p>I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs. </p>

<p>If we instead ask about <em>balanced</em> Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane graphs, is the problem still NP complete?</p>

<p>My intuition is that this extra requirement shouldn't make the problem easier, but maybe this feeling is naive since after all it means that the reduction has to be more intricate.</p>

CC BY-SA 4.0
2018-12-06T15:54:55.957Z
Your teacher posed a trick question. Think about it for a little while, and you will hit the solution.
Gamow
CC BY-SA 4.0
2018-12-06T17:41:13.473Z
@Gamow Oh, it appears that they are always balanced (?). (Easy to prove from the fact that maximal planar graphs with n vertices always have the same number of edges... I'll write this out.) Thank you!
Elle Najt
<cc.complexity-theory><graph-theory><np-complete><planar-graphs><hamiltonian-paths>
Is balanced Hamiltonian cycle NP complete on maximal plane graphs?
Elle Najt
# Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

(Asked by: username_0 on 2018-12-06)

I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs.

If we instead ask about *balanced* Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane graphs, is the problem still NP complete?

My intuition is that this extra requirement shouldn't make the problem easier, but maybe this feeling is naive since after all it means that the reduction has to be more intricate.

**Tags:** cc.complexity-theory, graph-theory, np-complete, planar-graphs, hamiltonian-paths
> **Comments:**
> **username_1**: Your teacher posed a trick question. Think about it for a little while, and you will hit the solution.  
> **username_0**: @Gamow Oh, it appears that they are always balanced (?). (Easy to prove from the fact that maximal planar graphs with n vertices always have the same number of edges... I'll write this out.) Thank you!  

---

## 1 answers

### Answer by username_0 on 2018-12-06. Score: 3 | Accepted answer

Yes, it is still $NP$ complete. This is because of:

Claim: All Hamiltonian cycles on maximal planar graphs are balanced.

Proof: This is a special case of Grinberg's theorem: <https://en.wikipedia.org/wiki/Grinberg%27s_theorem>


---

