Задача 098 — Задачи на Графы

В графе на 20 вершинах степень каждой вершины не более 3 . Какое наибольшее количество циклов длины 4 может быть в этом графе?

Подсказка

Возьмём любое ребро графа. Пусть оно входит в какой-либо цикл длины 4. Выбросим из этого цикла ребро, не имеющее с нашим общих вершин. Получится маршрут длины 3, где взятое нами ребро является средним из трёх, и цикл по этому маршруту восстанавливается однозначно.

Решение

Ответ: 27. Решение. Напомним, что через $K_{3,3}$ обозначается полный двудольный граф на 6 вершинах, то есть граф, три вершины которого можно покрасить в один цвет, а три — в другой так, что любые две одноцветные вершины будут соединены ребром, а любые две разноцветные — нет. В графе $K_{3,3} 9$ циклов длины 4, потому что цвета вершин в цикле чередуются, и по две вершины каждого цвета в $K_{3,3}$ можно выбрать $3 \times 3=9$ способами. Отсюда получается пример на 27 циклов: достаточно взять три графа $K_{3,3}$ , а из двух оставшихся вершин рёбер не проводить.

Покажем, что больше 27 циклов длины 4 в нашем графе не бывает Возьмём любое его ребро. Пусть оно входит в какой-либо цикл длины 4. Выбросим из этого цикла ребро, не имеющее с нашим общих вершин. Получится маршрут длины 3, где взятое нами ребро является средним из трёх, и цикл по этому маршруту восстанавливается однозначно. Но каждый из двух концов взятого нами ребра принадлежит, кроме него, максимум ещё двум рёбрам. Поэтому в нашем графе есть максимум $2 \times 2=4$ маршрута длины 3 , где взятое нами ребро является средним из трёх. Таким образом, через каждое ребро нашего графа проходит не более 4 циклов длины 4.

Назовём ребро хорошим, если оно входит ровно в 4 цикла длины 4 . Покажем, что если в компоненте связности нашего графа есть хотя бы одно хорошее ребро, то эта компонента имеет вид $K_{3,3}$ . В самом деле, в этом случае из каждой вершины нашего ребра должно выходить ещё 2 ребра, и каждый из вторых концов рёбер, выходящих из одной вершины, должен соединяться с каждым из вторых концов рёбер, выходящих из другой вершины. Получается $K_{3,3}$ , а наружу рёбра из него не ведут, потому что степень каждой вершины $K_{3,3}$ и так уже равна 3.

Пусть в нашем графе ровно $k \leq 2$ компонент связности вида $K_{3,3}$ . Тогда в нём $20-6 k$ вершин, входящих в «плохие» компоненты, где через каждое ребро проходит не более 3 циклов длины 4. В этих компонентах не более $3 \times(20-6 k) / 2=30-9 k$ рёбер и, стало быть, не более $3 \times(30-9 k) / 4=(90-27 k) / 4$ циклов длины 4, а всего в графе этих циклов не больше, чем $9 k+(90-27 k) / 4=22,5+9 k / 4 \leq 22,5+18 / 4=27$ . Если же в графе 3 компоненты связности вида $K_{3,3}$ , то в этих компонентах 27 циклов длины 4 , а две оставшиеся вершины, не будучи связанными с остальными 18 -ю, новых циклов длины 4 добавить не могут. Итак, циклов длины 4 у нас всегда не более 27.