Uma cobertura de vértices em um grafo é um conjunto de vértices que contém pelo menos uma das pontas de cada aresta. Em outras palavras, uma cobertura de vértices é um conjunto X de vértices dotado da seguinte propriedade: toda aresta do grafo tem pelo menos uma ponta em X.