Если в графе

с

вершинами минимальная степень вершины равна

, то
1) Для любого

существует такое множество вершин

, что в объединении

и множества вершин, не соединенных с ни с какой вершиной из
имеется не более

вершин.
2) Существует такое множество вершин

, что любая вершина из

соединена ребром с некоторой вершиной из

, при этом

Рассмотрим первый пункт.
Я так понимаю, что любое возможное ребро из множества

появляется независимо с вероятностью

.
То есть

для каждой вершины

Вероятность того, что из

ребер графа ровно

окажутся в множестве

равна

Пока что только такие идеи есть, больше не знаю за что зацепиться и как использовать минимальную степень вершины графа
