Изменения

Обозначим минимальное вершинное покрытие <tex>G</tex> как <tex>M</tex>. Пусть <tex>U = V(G) \setminus M</tex>. <br>Докажем <tex>(1) \Rightarrow (3)</tex>. Предположим, что в <tex>G</tex> существует наименьшее вершинное покрытие<tex>M</tex>, которое не является внешним.Это значит что <tex>\exists M' : \: M' = \{u_1, \dots, u_r \}, </tex> где <tex>r \leqslant \alpha_0(G)</tex>,такое что <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>.