200
правок
Изменения
→Критерий существования реберного ядра
Докажем <tex>(2) \Rightarrow (1)</tex>.
Пусть <tex>M = \{v_1, \dots, v_s\}</tex> {{---}} наименьшее внешнее вершинное покрытие. Пусть <tex>Y_i = \{u \mid u \in U, uv_i \in E(G) \}</tex>. Тогда для любого <tex>k: \:\: 1 \leqslant k \leqslant s</tex>, объединение любых <tex>k</tex> различных множеств <tex>Y_i</tex> содержит, по меньшей мере <tex>k</tex> вершин.
Следовательно, по теореме Холла<ref>P. Hall "On representatives of subsets" [https://math.dartmouth, 1935, pp.edu/archive/m38s12/public_html/sources/Hall193526-30.pdf]</ref>, существует множество <tex>s</tex> различных вершин <tex>\{y_1, \dots, y_s\}, \: y_j \in Y_j</tex>. Следовательно существует набор независимых ребер <tex>y_1v_1, \dots, y_sv_s</tex>. А значит <tex>C_1(G)</tex> не может быть пустым.
}}
[[Файл:EdgeCore.png|thumb|500px|рис. 1. a) граф <tex>H</tex>, б) реберное ядро графа <tex>H</tex> ]]
