Изменения

(1) <tex>G</tex> имеет не пустое рёберное ядро. <br>

такое что <tex>|M'| > |U(M')|.</tex> Пусть <tex>U(M') = \{u_1, \dots, u_t\}, \: t < r</tex>. Так же, пусть <tex>X</tex> {{---}} максимальное независимое множество ребер в <tex>G</tex>. Поскольку никакие две вершины <tex>U</tex> не смежны, каждое ребро из <tex>X</tex> соединено, по крайней мере, с одной вершиной из <tex>M</tex>. Если какое-нибудь ребро из <tex>X</tex> соединено более чем с одной ввершиной из <tex>M</tex>, то <tex>|X| < \alpha_0(G)</tex> и <tex>C_1(G) = \varnothing </tex>. Так что будем считать, что каждое ребро из <tex>X</tex> смежно ровно с одной вершиной из <tex>M</tex>. Из этого сдедует, что <tex>|X| \leqslant t - r + \alpha_0(g) \leqslant < \alpha_0(G)</tex>. И снова <tex>C_1(G) = \varnothing</tex>.<br>Следствие <tex>(3) \Rightarrow (2)</tex> {{---}} очевидно. <br>Докажем <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> вершин. Следовательно, по теореме Холла (о системах различных представителей), существует множество <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> не может быть пустым.