Teoria dos Grafos
Enviado: 09 Dez 2020, 15:53
Em um grafo de [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.
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]
se alguma aresta [tex3]u_iu_j[/tex3]
for da mesma cor que [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