200
правок
Изменения
→Реберное ядро в двудольном графе
Если оба конца ребра <tex>w \in E(G)</tex> покрыто некоторым минимальным вершинным покрытием, то <tex>w \notin C_1(G)</tex>.
|proof=
Сошлемся на теорему <tex>(3)</tex> аналогичного результата<ref>A. L. Dulmage, and N. S. Mendelsohn "Coverings of bipartite graphs"[https://cms.math.ca/openaccess/cjm/v10/cjm1958v10, 1958, pp.0517517-0534534.pdf]</ref> для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
}}
'''Следствие 1''' если <tex>G</tex> имеет минимальное вершинное покрытие, которое не является независимым, то <tex>G \neq C_1(G)</tex>.<br>
