Graph Concepts

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.

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.

	The red vertex covers the red edges.
	The red vertices form a vertex covering for this graph.

	The red edge covers the red vertices.
	The red edges are an edge covering for this graph.