Q3 Matemática  (Rioplatense Mathematical Olympiad, Level 3 2011)

Seja $M$ um mapa feito de várias cidades ligadas entre si por voos. Dizemos que existe uma rota entre duas cidades se houver um voo sem escalas ligando essas duas cidades. Para cada cidade a $M$ denotar por $M_a$ o mapa formado pelas cidades que possuem rota e rotas ligando essas cidades (para não fazer parte de $M_a$). As cidades de $M_a$ são divididas em dois conjuntos para que o número de rotas que ligam cidades de conjuntos diferentes seja máximo; chamamos esse número de corte de $M_a$. Suponha que para cada corte de $M_a$ , seja estritamente menor que dois terços do número de rotas $M_a$ . Mostre que para qualquer coloração das rotas $M$ com duas cores existem três cidades de $M$ unidas por três rotas da mesma cor.