**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. |

Copyright © 1999-2000 SciMathMN