Thread: Graph Theory
View Single Post
  #3  
Old 10-16-2007, 06:08 PM
blah_blah blah_blah is offline
Senior Member
 
Join Date: Feb 2007
Posts: 378
Default Re: Graph Theory

yes they are, no it's not trivial.

pick a vertex v, without loss of generality it has at least 6 adjacent edges of color c_1 of the form {vv1,vv2,...vv6}. If any of {v1v2,v2v3,...,v5v6} are colored c1, we're done. assume not, so that all of them get colors c2 or c3. by the friendship theorem, there is a monochromatic triangle in color c2 or c3 from {v1v2,v2v3,...,v5v6}, whence the result follows.
Reply With Quote