Olimpiada de Selección de Equipos de Rumania 2009 Problema 2

2 Demuestre que las aristas de un grafo planar simple finito (sin lazos ni aristas múltiples) pueden orientarse de tal manera que a lo sumo tres cuartos del número total de aristas de cualquier ciclo compartan la misma orientación. Además, muestre que esta es la mejor cota global posible. Comentario: El problema real en la TST pedía demostrar que las aristas pueden colorearse con $2$ colores de modo que se cumpla la misma conclusión. En esas circunstancias, el problema es erróneo y se encontró un contraejemplo en el concurso por Marius Tiba.

0

0

Kevin

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados