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

# FindVertexCover

 FindVertexCover[g] finds a vertex cover of the graph g with a minimum number of vertices.
• A vertex cover is a set of vertices that is incident to every edge.
Find a vertex cover in a complete graph:
Find a vertex cover in a directed graph:
Find a vertex cover in a complete graph:
 Out[1]=
 Out[2]=

Find a vertex cover in a directed graph:
 Out[1]=
 Out[2]=
 Scope   (2)
FindVertexCover works with undirected graphs:
Directed graphs:
The result of FindVertexCover can be tested by VertexCoverQ:
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