About MATtours
Site mapGallery of graphs and algorithmsHow to teach using investigationsClickable list of termsHelp

Coverings

A vertex covering of a graph is a collection, or set, of vertices that are incident to every edge in the graph. Of course, the set of all the vertices in the graph is a vertex covering. Minimal coverings, or coverings with the smallest number of vertices are often of interest.
The red vertex covers the red edges.
vertex covering The red vertices form a vertex covering for this graph.

Similarly, an edge covering of a graph is a collection, or set, of edges that are incident on every vertex in the graph.
The red edge covers the red vertices.
edge covering The red edges are an edge covering for this graph.

Copyright © 1999-2000 SciMathMN