Return to Question

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. **Is it always possible to choose a hamiltonian cycle so that at least one of the polygons has only two ears?**°° In fact, in most of the cases I investigated, it was possible to choose a hamiltonian cycle so that both polygons had no more than two ears, e.g. the Heawood graph on 25 vertices. With three or more degree 3 vertices in the maximal planar graph it's sometimes impossible for both polygons having no more than 2 ears.

(°) A Hamilton cycle visits each vertex once and returns in the startvertex. (°°) An ear of a triangulated polygon is a triangle with 2 of it's edges on the boundary.

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to choose a hamiltonian cycle so that at least one of the polygons has only two ears?°° In fact, in most of the cases I investigated, it was possible to choose a hamiltonian cycle so that both polygons had no more than two ears, e.g. the Heawood graph on 25 vertices. With three or more degree 3 vertices in the maximal planar graph it's sometimes impossible for both polygons having no more than 2 ears.

(°) A Hamilton cycle visits each vertex once and returns in the startvertex. (°°) An ear of a triangulated polygon is a triangle with 2 of it's edges on the boundary.

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible that one of those polygons has no more than two ears°°? In fact, in most of the cases I investigated, it was possible that both polygons had no more than two ears, e.g. the Heawood graph on 25 vertices. With three or more degree 3 vertices in the maximal planar graph it's sometimes impossible for both polygons having no more than 2 ears.

(°) A Hamilton cycle visits each vertex once and returns in the startvertex.

 (°°) An ear of a triangulated polygon is a triangle with 2 of it's edges on the boundary.

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. **Is it always possible to choose a hamiltonian cycle so that at least one of the polygons has only two ears?**°° In fact, in most of the cases I investigated, it was possible to choose a hamiltonian cycle so that both polygons had no more than two ears, e.g. the Heawood graph on 25 vertices. With three or more degree 3 vertices in the maximal planar graph it's sometimes impossible for both polygons having no more than 2 ears.

(°) A Hamilton cycle visits each vertex once and returns in the startvertex.  (°°) An ear of a triangulated polygon is a triangle with 2 of it's edges on the boundary.

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible that one of those polygons has no more than two ears°°? In fact, in most of the cases I investigated, it was possible that both polygons had no more than two ears, e.g. the Heawood graph on 25 vertices. With three or more degree 3 vertices in the maximal planar graph it's sometimes impossible for both polygons having no more than 2 ears.

(°) A Hamilton cycle visits each vertex once and returns in the startvertex.

(°°) An ear of a triangulated polygon is a triangle with 2 of it's edges on the boundary.

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible that one of those polygons has no more than two ears°°? In fact, in most of the cases I investigated, it was possible that both polygons had no more than two ears, e.g. the Heawood graph on 25 vertices. With three or more degree 3 vertices in the maximal planar graph it's sometimes impossible for both polygons having no more than 2 ears.

(°) A Hamilton cycle visits each vertex once and returns in the startvertex.

(°°) An ear of a triangulated polygon is a triangle with 2 of it's edges on the boundary.