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