Task list filter?
Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.
Task rankings
Difficulty level
Task tags
Task type
«
«
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.