This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.2)

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:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
 
Find a vertex cover in a directed graph:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[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