Участник:Masha
Формула Бержа
Лемма: |
, где - граф с вершинами, |
Доказательство: |
Удалим из графа В сумме множество , получим компонент связности, содержащих вершин соответсвенно. т. к в сумме это все вершины исходного графа . Возьмем данное равенство по модулю два: число единиц равно числу нечетных компонент . Таким образом, . |
Теорема: |
Доказательство: |
2) Если , тогда рассмотрим исходный граф и полный граф с вершинами, множество вершин нового графа обозначим как . Каждую вершину вспомогательного графа соединим с каждой вершиной . Получим новый граф , докажем, что для него выполнено условие Татта. Докажем, что . Рассмотрим .Если не , тогда посколько граф полный, и все его вершины связаны с каждой вершиной графа , то граф связный и или . В случае условие очевидно выполняется т.к . Рассмотрим случай , , где . Разность имеет ту же четность, что и , поэтому четно, значит, по лемме мощность нечетна, следовательно, она не равна нулю, значит .Если Таким образом, для графа , то . выполнено условие Татта, следовательно, в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе , удалим вершины из графа . Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин , значит, . Удалим множество вершин из графа . Заметим, что после удаление в графе осталось несколько нечетных компонент и образовались новые непокрытые вершины, но при этом осталось на k больше нечетных компонент, чем мы удалили, значит, хотя бы k нечетных компонент содержали исходно непокрытую вершину, значит, . Значит, . Теорема доказана. |