Graph nonexistence

Task number: 4193

Show that there is no Eulerian planar graph whose faces are one five-cycle and otherwise only triangles.

  • Solution

    We will use the coloring of the faces with white and black such that the adjacent faces have different colors (see the previous problem).

    Without loss of generality, assume that the pentagon is colored white. The number of edges on the border of black faces (triangles only) is a multiple of three, but the number of edges at the boundary of the white faces is congruent to \(5 \pmod 3 \).

    These two numbers cannot be equal, so there is no such graph.

Difficulty level: Moderate task
Solution require uncommon idea
Cs translation
Send comment on task by email