Изменения
→Критерий существования реберного ядра
{{Определение|
definition=
Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним''' (англ. ''external vertex cover''), если для любого подмножества <tex>M' \subseteq M</tex> выполняется неравнство <tex>|M'| \leqslant |U(M')|</tex>, где <tex>U(M') = \{v| \mid \:v \in V(G) \setminus M, \: vu \in E(G), \: u \in M'\}</tex>.
}}
{{Теорема|
}}
[[Файл:EdgeCore.png|thumb|500px|рис. 1. a) граф <tex>H</tex>, б) реберное ядро графа <tex>H</tex> ]]
В качестве примера рассмотрим граф <tex>H </tex> изображенный на рис. 1 а). Этот граф имеет два наименьших вершинных покрытия: <tex>M_1 = \{B, E, F\}</tex> и <tex>M_2 = \{B, E, G\}</tex>.
Пусть <tex>M_1' = M_1</tex> то <tex>U(M_1') = \{A, C, D, G\}</tex>. Пусть <tex>M_1'' = \{E, F\}</tex>. Тогда <tex>U(M_1'') =\{C, D, G\}</tex>.
Отсюда <tex>|M_1'| \leqslant |U(M_1')|</tex> и <tex>|M_1''| \leqslant |U(M_1'')|</tex>. И это верно для любого подмножества <tex>M_1</tex>. Значит, <tex>M_1</tex> {{---}} внешнее покрытие. Значит и <tex>M_2</tex> {{---}} внешнее покрытие.
