Re: Graph Theory
Here is my proof . It uses the pigeonhole principle .
Pick any vertex . There are 16 edges emanating from that vertex . From the pigeonhole principle there exists 6 edges of the same color . (16/3>=5) . Lets say it is red .
Now pick a vertex from one of the 6 edges different from the original vertex . There are 5 lines that emanate from that vertex and so 3 of them have to be the same color . Lets say it is blue . Now the endpoints of the blue edges form a triangle that must be monochromatic . Do you see why ?
|