# VertexCoverQ

VertexCoverQ[g,vlist]

yields True if the vertex list vlist is a vertex cover of the graph g, and False otherwise.

# Details

• A vertex cover is a set of vertices that are incident to every edge.
• VertexCoverQ works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

# Background & Context

• VertexCoverQ tests if a specified set of vertices forms a vertex cover for a given graph, where a vertex cover is a set of vertices satisfying the condition that each edge of the graph is incident to some vertex in the set. VertexCoverQ returns True if the set is a vertex cover and False otherwise.
• The entire vertex set of a graph is always a vertex cover (of maximum possible size). The smallest possible vertex cover for a given graph is known as a minimum vertex cover, and its size is known as the vertex cover number.
• Vertex covers are closely related to independent vertex sets (which are sets of vertices having the property that no two vertices are part of the same edge). In particular, a set of vertices is a vertex cover if and only if its complement forms an independent vertex set. As a result, the counts of vertex covers and independent vertex sets in a graph are the same.
• FindVertexCover can be used to find a single minimum vertex cover or a single vertex cover of any fixed size, but not all vertex covers. A trivial implementation for finding all vertex covers of a graph can be constructed by applying VertexCoverQ to all subsets of a graph's vertices. EdgeCoverQ performs the analogous test to VertexCoverQ for edge covers of a graph. FindIndependentVertexSet can be used to find one or more maximal independent vertex sets in a graph (each of whose complements is a vertex cover).

# Examples

open allclose all

## Basic Examples(2)

Test whether a set of vertices is a vertex cover in a graph:

 In[1]:=
 Out[1]=

Not all set of vertices are vertex covers in a graph:

 In[1]:=
 Out[1]=