Немного про задачу P4 с IZHO26 (решал её во время купаловки в океане, кайф 🌊) Часто в листиках для младших классов по темам "Графы. Связность" или "Остовные деревья" используют следующую задачу. В связном графе 100 вершин и 199 рёбер. Докажите, что в этом графе найдётся цикл такой, что остовный подграф без этого цикла связен. Решение: выделить остовное дерево и найти цикл на рёбрах, не состоящих в этом дереве. Ресёрческий майндест обычно заставляет нас залезать чуть глубже и задавать вопрос экстремально: какое наименьшее число рёбер нам гарантирует это свойство? Я даже немного удивлён, что не видел такого в листиках 🗿 При этом задачу это особо не усложняет, можно использовать в качестве пункта "б". Решение: остовное дерево можно выделить так, чтобы оно забирало все рёбра от одной из вершин, тогда 198 рёбер нам будет достаточно. При этом для 197 рёбер условие не выполнено: можно взять две вершины степени 99 и остальные вершины степени 2. Добавлю её в копилку 🤡