A vertex cover is a set of vertices meeting every edge of a graph. The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size has a vertex cover of size at most .
Articles by others on the same topic
In graph theory, a **vertex cover** of a graph is a set of vertices such that every edge in the graph is incident to at least one vertex from this set. In simpler terms, for every edge that connects two vertices, at least one of those vertices must be included in the vertex cover. The concept of a vertex cover is important in various areas of computer science, including optimization, network theory, and computational biology.