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.|
|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.|
|The red edges are an edge covering for this graph.|
Copyright © 1999-2000 SciMathMN