All faces of a polyhedron are triangles. Each of the vertices of this polyhedron is assigned independently one of three colors : green, white or black. We say that a face is Extremadura if its three vertices are of different colors, one green, one white and one black. Is it true that regardless of how the vertices's color, the number of Extremadura faces of this polyhedron is always even?
Problem
Source: Spanish Mathematical Olympiad, 2015, Problem 4
Tags: polyhedron, Graph coloring, combinatorics
01.05.2015 00:35
In each face of the polyhedron write the number of its edges connecting vertices of different colors. For an extremadura face this number will be 3, and for any other face it will be 2 or 0. The sum of the numbers on the faces is then twice the number of such edges (since each edge is part of two faces). But this number is even, and each non-extremadura face contributes an even number, so the sum of the numbers on extremadura faces is even, and thus the number of extremadura faces must be even.
03.03.2023 23:53
Consider changing a vertex of colour, WLOG from green to white, consider the colours of al vertices adjacent to our original one and enumerate them such that cyclically everyone of them is adjacent to the next and previous one. The numer of Extremadura faces is equal to the number of consecutive pairs of black-white if the vertex is green or black-green if the vertex is white. Consider each consecutive sequence of black vertices in our list, then each of them generate two black-white pairs, two black-green pairs or one of each. Then we can see the number of black-green pairs has the same parity of the number of black-white pairs, so changing the original vertex of colour preserves parity of the number of Extremadura faces. If every vertex is green we have 0 Extremadura faces, and from every state we can reach that changing every vertex not green to green, so the number of Extremadura faces is even.
15.01.2024 21:11
we prove this by induction . for the base case consider a tetrahedron .Now it can only have 0 or 2 extermadura. now we assume that the hypothesis it true for all polyhedrons with n-1 vertecies. now we add a vertex to the polyhedron. The vertex will joined to 3 other vertices giving us 3 new faces and one face will be removed. if the removed face was a extermadura then we will get a new extramadura(this doesn't change the number on extramadura) . Else we will either get 0 or 2 extramaduras. so the total number will remain even for n vertices . this completes the induction. And we are done (Credits: Chirag Goyal )