Each diagonal of the base and each lateral edge of a $9$-gonal pyramid is colored either green or red. Show that there must exist a triangle with the vertices at vertices of the pyramid having all three sides of the same color.
Problem
Source: Bulgaria 1980 P3
Tags: geometry, 3D geometry, pyramid, graph theory
30.11.2021 20:00
Since we have $10$ vertices with every possible connection, this can be thought of as the complete graph $K_{10}$. The sum of all degrees $D$ is $E*2 = {9\choose2} * 2 = 72$. Since we only use $2$ colors, by pidgeonhole, the sum of degrees of some color must be at least $\lceil \frac{72}{2}\rceil = 36$ (WLOG we say it is red). By pidgeonhole again, some vertex must have at least $\lceil \frac{36}{9} \rceil = 4$ red edges coming off of it. Consider any $3$ of the red edges. Either, 1. There is another red edge connecting the ends of our edges, and we have a triangle that is only red. 2. There are only green edges connecting the ends of our red edges. Since these edges must connect to each other, we have a green triangle. Remark Ramsey's theorem generalizes this, and it can be shown that only $K_{6}$ is required for two colors to necessarily form a monochromatic triangle.
30.09.2024 14:47
Kartoonpanda wrote: Since we have $10$ vertices with every possible connection, this can be thought of as the complete graph $K_{10}$... It's not a complete graph since only the diagonals of the base are colored (not the sides). Nevertheless, a similar idea works - there are 5 monochrome edges incident to the top vertex of the pyramid. It remains to see that among any 5 vertices of the base, there are 3 such that any 2 of them do not lie on the same side.