Consider the triangles one at a time and, in each, color red the shortest side. Some of the segments may well be colored repeatedly. Paint the remaining segments in blue. This brings us to a situation of a complete graph with 6 nodes all of whose edges are colored in one of two colors. As was mentioned elsewhere and will be shown shortly, there is always a monochromatic triangle. In our situation it must be all red, because an all-blue triangle still needs to have a shortest side which then would have been painted red. In an all-red triangle there is a longest side of course. But being painted red means that in another triangle it is the shortest.
Now let's prove that a bichromatic complete graph with 6 nodes has a monochromatic triangle. An arbitrary node in a complete graph is linked by the edges to all the remaining nodes - 5 for K6. Out of five edges painted in two colors, there are at least three painted in the same color. For example, assume that there are three red edges incident with the same node. These red edges have three "free" ends that are joined by another triple of edges. There are just two possibilities:
- All of the three edges are painted blue, or
- one of them is painted red.
In the first case, there is an all-blue triangle. In the second, there is an all-red triangle.
References
- S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003
|Contact|
|Front page|
|Contents|
|Up|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
