FindVertexCover

FindVertexCover[g] finds a vertex cover of the graph g with a minimum number of vertices.

Examples

Find minimum vertex cover:

g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4}]
FindVertexCover[g]
(* {2, 3} *)

For a complete graph:

FindVertexCover[CompleteGraph[4]]
(* {1, 2, 3} *)

Please visit the official Wolfram Language Reference for more details.