Yummy triangles
Task number: 4559
Consider a planar drawing of a graph \(G\) in which all faces are triangles. Suppose, moreover, that each vertex contains either a cake, an ice cream, or a lollipop. We say a face is yummy, if all three sweets can be found on its vertices (i.e., each just once). Show that there are an even number of yummy faces.
Hint
Explore how faces can be adjacent to each other across edges with different sweets at their ends.Solution
Let us look at the subgraph of the dual induced by the edges corresponding to edges with different sweets at their ends in the original graph.
The vertices of the dual can be of degree 3, these correspond to yummy triangles. The other triangles in the dual correspond to vertices of degree 0 (all the same sweet) or degree 2 (one sweet twice and the other once).
Since by the parity principle every graph has an even number of vertices of odd degree, this graph has an even number of vertices of degree 3. So the original graph had an even number of yummy faces.
