Доказательство. Проведем доказательство, определив процедуру построения ядра K для произвольного неориентированого графа G = (V

Проведем доказательство, определив процедуру построения ядра K для произвольного неориентированого графа G = (V, U), не имеющего петель.

1. Положим K = .

2. Возьмем произвольную вершину v Î V, которая не является соседней с вершинами из K. Добавим v к множеству K.

3. Продолжаем процесс добавления вершин к множеству K до тех пор, пока в V имеются вершины, не являющиеся соседними с вершинами, включенными в K.

Так как множество V является конечным, то через конечное число шагов приведенная процедура заканчивает свою работу. При этом множество K является ядром графа G, поскольку по построению никакие две вершины из K не являются соседними, а всякая вершина из V \ K не может быть несоседней для хотя бы одной вершины из K.