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.
