wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> R(C_2m, C_2m, C_2m)
        
(Message started by: Aryabhatta on Jun 8^th, 2007, 2:47pm)

Title: R(C_2m, C_2m, C_2m)
Post by Aryabhatta on Jun 8^th, 2007, 2:47pm

Supposedly this problem appeared in Vietnamese Maths Olympiad.

Find the largest n, such that :

There is a three colouring of the edges of the complete graph K_n on n vertices with no monochromatic cycle of even length.

Title: Re: R(C_2m, C_2m, C_2m)
Post by Aryabhatta on Jun 17^th, 2007, 11:24am

Hint: [hide] Show that any simple graph on n vertices and more than [3(n-1)/2] edges has an even cycle[/hide]