WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

VertexCoverQ
✖
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)Summary of the most common use cases

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-q8vqy
Out[1]=1

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-khmgs5
Out[1]=1

Scope  (6)Survey of the scope of standard use cases

Test undirected graphs:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-c4jban
Out[1]=1

Directed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-d92a8t
Out[1]=1

Multigraphs:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-15kl6n
Out[1]=1

Mixed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-czvddh
Out[1]=1

VertexCoverQ gives False for expressions that are not graphs:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-3l2bwe
Out[1]=1

VertexCoverQ works with large graphs:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-hlltv6
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-hrht0p
Out[2]=2

Applications  (2)Sample problems that can be solved with this function

Enumerate all vertex covers for a cycle graph:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-k7ld2c
Out[1]=1

Enumerate all subsets of vertices and select the ones that are covers:

In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-hyw7qp
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-htjso
Out[3]=3

Highlight covers:

In[4]:=4
✖
https://wolfram.com/xid/0dc3e0saikzn-b9l00i
Out[4]=4

Enumerate all minimum vertex covers for a Petersen graph:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-hiv33l
Out[1]=1

Find the size of a minimum vertex cover:

In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-zjd84
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-mqn8zl
Out[3]=3

Enumerate all minimum vertex covers:

In[4]:=4
✖
https://wolfram.com/xid/0dc3e0saikzn-c7l5n7
Out[4]=4

Highlight minimum covers:

In[5]:=5
✖
https://wolfram.com/xid/0dc3e0saikzn-nuwksv
Out[5]=5

Properties & Relations  (7)Properties of the function, and connections to other functions

The VertexList of a graph is a vertex (typically non-minimal) cover:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-cou4t4
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-jhwg5r
Out[2]=2

A smallest vertex cover can be found using FindVertexCover:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-fds0n0
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-habyrc
Out[2]=2

A set of vertices is a vertex cover iff its complement is an independent set:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-8asoh
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-cj29j9
Out[2]=2

Check that the complement set of vertices is independent:

In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-jg28gl
Out[3]=3

The total size of the vertex cover and the largest independent set equals the vertex count:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-dme9ws
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-grp108
Out[2]=2

The complement of the vertex cover in GraphComplement is a clique in its original graph:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-d0kb5r
Out[1]=1

Compute the complement using the same embedding:

In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-eblt1f
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-d1c34
Out[3]=3

Its complement is a clique:

In[4]:=4
✖
https://wolfram.com/xid/0dc3e0saikzn-ed5oub
Out[4]=4
In[5]:=5
✖
https://wolfram.com/xid/0dc3e0saikzn-qfwrfz
Out[5]=5
In[6]:=6
✖
https://wolfram.com/xid/0dc3e0saikzn-fbxu48
Out[6]=6

The complete bipartite graph has a vertex cover of size :

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-ex4zx8
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-idoe5c
Out[2]=2

The largest independent edge set in a bipartite graph has the same size as the smallest vertex cover:

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-ecgbva
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-bicsi8
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-hcbva
Out[3]=3
Wolfram Research (2010), VertexCoverQ, Wolfram Language function, https://reference.wolfram.com/language/ref/VertexCoverQ.html (updated 2014).
✖
Wolfram Research (2010), VertexCoverQ, Wolfram Language function, https://reference.wolfram.com/language/ref/VertexCoverQ.html (updated 2014).

Text

Wolfram Research (2010), VertexCoverQ, Wolfram Language function, https://reference.wolfram.com/language/ref/VertexCoverQ.html (updated 2014).

✖
Wolfram Research (2010), VertexCoverQ, Wolfram Language function, https://reference.wolfram.com/language/ref/VertexCoverQ.html (updated 2014).

CMS

Wolfram Language. 2010. "VertexCoverQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/VertexCoverQ.html.

✖
Wolfram Language. 2010. "VertexCoverQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/VertexCoverQ.html.

APA

Wolfram Language. (2010). VertexCoverQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/VertexCoverQ.html

✖
Wolfram Language. (2010). VertexCoverQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/VertexCoverQ.html

BibTeX

@misc{reference.wolfram_2025_vertexcoverq, author="Wolfram Research", title="{VertexCoverQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/VertexCoverQ.html}", note=[Accessed: 26-April-2025 ]}

✖
@misc{reference.wolfram_2025_vertexcoverq, author="Wolfram Research", title="{VertexCoverQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/VertexCoverQ.html}", note=[Accessed: 26-April-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_vertexcoverq, organization={Wolfram Research}, title={VertexCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/VertexCoverQ.html}, note=[Accessed: 26-April-2025 ]}

✖
@online{reference.wolfram_2025_vertexcoverq, organization={Wolfram Research}, title={VertexCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/VertexCoverQ.html}, note=[Accessed: 26-April-2025 ]}