Рассмотрим следующий неориентированный граф: 
Множество вершин {2,4,5} является минимальным покрытием вершин графа.Зачем?потому что это покрытие вершин (все ребра покрыты), и нет другого покрытия вершин с меньшим количеством вершин.
Множество вершин {2,3,5,6,7} представляет собой минимальное покрытие вершин.Зачем?потому что это покрытие вершин, и любое нетривиальное подмножество {2,3,5,6,7} не является покрытием вершин.Попробуйте удалить любую вершину из {2,3,5,6,7} и убедитесь, что вы оставили непокрытый край.Что делает покрытие вершины минимальным, так это неспособность уменьшить его.Вы не можете сделать набор меньшим, чем он есть, и по-прежнему получать покрытие вершин (не вставляя в него вершины).
Очевидно, что данное минимальное покрытие вершин не является минимальным покрытием вершин, потому что минимальное покрытие вершин имеет три вершины, а наше минимальное покрытие вершин имеет 5 вершин.Следовательно, не каждое минимальное покрытие вершин также является минимальным покрытием вершин.
Каждое минимальное покрытие вершин также является минимальным покрытием вершин, поскольку удаление вершин из минимального покрытия вершин приведет к набору вершин размера, меньшегоминимальное покрытие.Таким образом, любое нетривиальное подмножество минимального покрытия вершин не является покрытием вершин, поэтому минимальное покрытие вершин также минимально.