Olimpíadas ⇒ Teoria dos Grafos Tópico resolvido

[goncalves3718]

Em um grafo de [tex3]17[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]17[/tex3]

vértices todas as arestas são traçadas e pintadas de uma de três cores. Prove que existe um triângulo com as três arestas da mesma cor.

[leozitz]

esse problema pede para provar que R(3, 3, 3) <= 17, vamos começar que nem como fizemos no caso R(3, 3)
olhando para um vértice v, ele tem 16 arestas ligadas a ele, por PCP a gente tem uma cor que tem pelo menos 6 arestas dessa cor ligada a v, vamos chamar as outras pontas dessa arestas de [tex3]u_i, 1 \le i\le 6[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]u_i, 1 \le i\le 6[/tex3]

se alguma aresta [tex3]u_iu_j[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]u_iu_j[/tex3]

for da mesma cor que [tex3]u_iv[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]u_iv[/tex3]

que digamos que seja verde, o problema acaba, então vamos supor que todas as arestas tem cor diferente de verde, agora queremos provar que em um K_6, quando pintado com 2 cores temos um triangulo, mas isso é verdade, pois já provamos que R(3, 3) = 6

problema que eu menciono na solução
viewtopic.php?f=20&t=90524&p=285115#p285115