Граф с бесконечным числом вершин

[Randomas]

Задача. Дан граф, в котором бесконечно много вершин. Доказать, что можно выбрать бесконечное подмножество вершин, попарно соединённых или бесконечное подмножество попарно не соединённых.

Моё решение. Если в графе бесконечное число компонент связности, то выбираем в каждой компоненте по вершине, между ними нет рёбер. В противном случае берём компоненту с бесконечным числом вершин, выбираем любую вершину и смотрим на расстояние (в минимальном количестве рёбер) от неё до всех других вершин из этой компоненты. Если будет бесконечно много вершин на расстоянии больше 1, то отбираем эту вершину и повторяем процедуру для подграфа из несвязанных с ней вершин. Возможные варианты:
.) На каком-то шаге получим бесконечное число копонент связности.
.) На каком-то шаге все вершины будут на расстоянии 1 от любой выбранной. Значит, мы нашли полный подграф.
.) Процесс можно продолжать бесконечно. Тогда между отобранными вершинами нет рёбер.

Собственно, вопрос. Есть ощущение некоторой "дуальности". Можно рассмотреть граф на тех же вершинах, в котором рёбра есть только там, где их нет в исходном. "Дуальное" утверждение будет таким же. Можно ли построить решение, которое на этом основывается? Или это глупая идея? Есть ли примеры из других областей, где какая-то похожая "дуальность" содержательно используется?

[Geen]

Randomas в сообщении #1616370 писал(а):

Если будет бесконечно много вершин на расстоянии больше 1

А если нет?

[mihaild]

Randomas в сообщении #1616370 писал(а):

Если будет бесконечно много вершин на расстоянии больше 1

Randomas в сообщении #1616370 писал(а):

На каком-то шаге все вершины будут на расстоянии 1 от любой выбранной

А где случай, когда от любой вершины конечное число вершин на расстоянии больше 1? Например граф на натуральных числах, где ребрами соединены числа, отличающиеся не меньше чем в 2 раза.
В нём конечно можно найти клику, но вроде бы в Вашей процедуре это не описано.

[Randomas]

Да, уже понял и нашёл решение. В нём можно поменять "соеденены" и "не соеденены" - именно то, что я хотел. Спасибо, вопрос закрыт.