Tutup verteks

Dalam kasus "minimum vertex cover", permasalahan ini dapat dibuat sederhana. Di mana terdapat M jumlah "minimum" dari "vertex cover".
Ada beberapa graf khusus yang dapat langsung diketahui berapa jumlah "vertex cover"-nya. Graf tersebut adalah graf star dan graf lengkap.