Vertex cover in hypergraphs

The set of blue vertices (vertices 2, 5 and 9) is a minimum vertex-cover, as there are no smaller sets of vertices which are able to be a part of every hyperedge. The vertex-coloring number of the graph is therefore 3, the number of vertices in the minimum vertex-cover.

The set of green vertices (vertices 1, 3, 7 and 10) is a minimal vertex-cover, as removing any vertex from this set makes the remaining set no longer a vertex cover at all.

Note that the term transversal would exclude the green set under its stricter definition, as edge 5 contains both vertex 3 and 10.

In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph.

An equivalent term is a hitting set: given a collection of sets, a set which intersects all sets in the collection in at least one element is called a hitting set. The equivalence can be seen by mapping the sets in the collection onto hyperedges.

Another equivalent term, used more in a combinatorial context, is transversal. However, some definitions of transversal require that every hyperedge of the hypergraph contains precisely one vertex from the set.