This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.

# VertexCoverQ

 VertexCoverQ yields True if the vertex list vlist is a vertex cover of the graph g, and False otherwise.
• A vertex cover is a set of vertices that is incident to every edge.
Test whether a set of vertices is a vertex cover in a graph:
Test for a directed graph:
Test whether a set of vertices is a vertex cover in a graph:
 Out[1]=
 Out[2]=

Test for a directed graph:
 Out[1]=
 Out[2]=
 Scope   (2)
Test undirected graphs:
Directed graphs:
 Applications   (2)
Enumerate all vertex covers for a cycle graph:
Enumerate all subsets of vertices and select the ones that are covers:
Highlight covers:
Enumerate all minimal vertex covers for a Petersen graph:
Find the size of a minimal vertex cover:
Enumerate all minimal vertex covers:
Highlight minimal covers:
The VertexList of a graph is a vertex (typically non-minimal) cover:
A smallest vertex cover can be found using FindVertexCover:
A set of vertices is a vertex cover iff its complement is an independent set:
Check that the complement set of vertices is independent:
The total size of the vertex cover and the largest independent set equals the vertex count:
The complement of the vertex cover in GraphComplement is a clique in its original graph:
Compute the complement using the same embedding:
Its complement is a clique:
The complete bipartite graph has vertex cover of size :
The largest independent edge set in a bipartite graph has the same size as the smallest vertex cover:
New in 8