WOLFRAM

Wolfram Language & System Documentation Center

VertexCoverQ[g,vlist]

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

Details
Details and Options Details and Options
Background & Context
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

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 all close all

Basic Examples  (2)

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

Wolfram Language code: VertexCoverQ[[image], {2, 3, 6}]

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

Wolfram Language code: VertexCoverQ[[image], {1, 4}]

Scope  (6)

Test undirected graphs:

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

Directed graphs:

Wolfram Language code: VertexCoverQ[[image], {2, 3, 6}]

Multigraphs:

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

Mixed graphs:

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

VertexCoverQ gives False for expressions that are not graphs:

Wolfram Language code: VertexCoverQ[x, {1, 3}]

VertexCoverQ works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: VertexCoverQ[g, {1, 2}]//Timing

Applications  (2)

Enumerate all vertex covers for a cycle graph:

Wolfram Language code: g = CycleGraph[4, VertexSize -> Small]

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

Wolfram Language code: Subsets[VertexList[g]]
Wolfram Language code: vcl = Select[%, VertexCoverQ[g, #]&]

Highlight covers:

Wolfram Language code: Table[HighlightGraph[g, h], {h, vcl}]

Enumerate all minimum vertex covers for a Petersen graph:

Wolfram Language code: g = PetersenGraph[5, 2, VertexSize -> Medium]

Find the size of a minimum vertex cover:

Wolfram Language code: FindVertexCover[g]
Wolfram Language code: n = Length[%]

Enumerate all minimum vertex covers:

Wolfram Language code: vcl = Select[Subsets[VertexList[g], {6}], VertexCoverQ[g, #]&]

Highlight minimum covers:

Wolfram Language code: Table[HighlightGraph[g, h], {h, vcl}]

Properties & Relations  (7)

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

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: VertexCoverQ[%, VertexList[%]]

A smallest vertex cover can be found using FindVertexCover:

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: VertexCoverQ[%, FindVertexCover[%]]

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

Wolfram Language code: g = GridGraph[{2, 3}]
Wolfram Language code: vc = FindVertexCover[g]

Check that the complement set of vertices is independent:

Wolfram Language code: IndependentVertexSetQ[g, Complement[VertexList[g], vc]]

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

Wolfram Language code: g = WheelGraph[8]
Wolfram Language code: Length[FindVertexCover[g]] + Length[First[FindIndependentVertexSet[g]]] == VertexCount[g]

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

Wolfram Language code: g = GridGraph[{2, 3}]

Compute the complement using the same embedding:

Wolfram Language code: h = GraphComplement[g, VertexCoordinates -> GraphEmbedding[g]]
Wolfram Language code: FindVertexCover[h]

Its complement is a clique:

Wolfram Language code: Complement[VertexList[g], FindVertexCover[h]]
Wolfram Language code: Subgraph[g, %]
Wolfram Language code: CompleteGraphQ[%]

The complete bipartite graph has a vertex cover of size :

Wolfram Language code: CompleteGraph[{2, 4}]
Wolfram Language code: Length[FindVertexCover[%]] == Min[2, 4]

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

Wolfram Language code: g = CycleGraph[6]
Wolfram Language code: BipartiteGraphQ[g]
Wolfram Language code: Length[FindVertexCover[g]] == Length[FindIndependentEdgeSet[g]]
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).

CMS

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

BibTeX

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

BibLaTeX

@online{reference.wolfram_2026_vertexcoverq, organization={Wolfram Research}, title={VertexCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/VertexCoverQ.html}, note=[Accessed: 13-June-2026]}