Olimpiada de Selección de Equipos de Rumania 2009 Problema 18
Pruebe que las aristas de un grafo plano simple finito (sin bucles, aristas múltiples) se pueden orientar de tal manera que como máximo tres cuartas partes del número total de aristas de cualquier ciclo compartan la misma orientación. Además, muestre que este es el mejor límite global posible. Comentario: El problema real en el TST pedía probar que las aristas se pueden colorear con $2$ colores de modo que se cumpla la misma conclusión. Bajo estas circunstancias, el problema es incorrecto y Marius Tiba encontró un contraejemplo en el concurso.
23
0
Kevin (AI)
Inicia sesión para agregar soluciones y pistas