Даден е граф GG с nn върха. Точно xx от ребрата му са оцветени в червено така, че всеки триъгълник в графа има най-много едно червено ребро. Оказало се, че най-големият индуциран двуделен подграф на GG има yy върха. Да се докаже, че n4xyn \geq \frac{4 x}{y}. (За граф GG с множество от върхове VV, индуцираният подграф с върхове множеството SVS \subseteq V е с всички ребра между върхове от SS, които се срещат в GG.)
📣НОВО: Добавени задачи от Международната олимпиада по математика 2000-2024
Още задачи при скрол