# Two ears polygon in a maximal planar hamiltonian graph

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.

• Your use of "possible" and "impossible" is confusing, and "one" is also unclear. Does your bold sentence mean "Is it always possible to choose a hamiltonian cycle so that at least one of the polygons has only two ears?" (After noting that less than two ears never happens; this is equivalent to a non-trivial tree having at least two leaves.) Commented Mar 4, 2023 at 1:06
• @Brendan: Yes, the bold sentence is the question. And in fact I'm only interrested in it for maximal planar polygons without separating triangles. What follows (included the drawings) is peripheral information, not essential for it. And of coarse a trangulated planar polygon has at least two ears (Gary Meister, 1975 and Max Dehn circa 1899, Wikipedia). Commented Mar 4, 2023 at 10:12
• @Brendan: Now I understand the confusion. Your question is what I mean. It's corrected. Excuses. Commented Mar 4, 2023 at 17:14

Carol Zamfirescu and Gunnar Brinkmann have informed me that this paper answers the question.

• Thanks, Brendan, Gunnar and Carol. For me it's the best answer up to now, although!. Is it also valuable for more than 130 triangles? Is it also valuable for more than 21 vertices without separating triangles (degree 4 or 5 graphs)? Commented Mar 5, 2023 at 12:13