MinimumVertexCover returns a list of vertices which comprise a minimum vertex cover.

VertexCoverNumber returns the number of vertices in a minimum vertex cover of the graph G.

A vertex cover of a graph G is a subset S of the vertices of G such that every edge in G is incident to some member of S.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{GraphComplement}\left(\mathrm{CompleteGraph}\left(3\,4\right)\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 7\; vertices\; and\; 9\; edge(s)}$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{VertexCoverNumber}\left(G\right)$

$5$

$\mathrm{MinimumVertexCover}\left(G\right)$

$\left[2\,3\,5\,6\,7\right]$

The GraphTheory[MinimumVertexCover] and GraphTheory[VertexCoverNumber] commands were introduced in Maple 2019.

For more information on Maple 2019 changes, see Updates in Maple 2019.