Докажите, что любое минимальное покрытие вершин клики размера n должно иметь ровно n-1 вершин.

Question

Как доказать, что любое минимальное покрытие вершин клики размера n должно иметь ровно n-1 вершин? Спасибо

Answer 1

Если есть две вершины из клики, не входящей в набор, то ребро между ними не покрыто, поэтому любое покрытие должно иметь как минимум n-1 вершин. Любое подмножество n-1 вершин является тривиальным накрытием.