Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 68 · Graph Theory

Independent Sets, Vertex Covers, Edge Covers and Matchings

Learn independent sets, vertex covers, edge covers and matchings, the identities that link them, and how maximal differs from maximum, with Python.

Four questions about a graph sound different but are tightly linked. Which largest group of vertices has no edge between any two of them? Which smallest group of vertices touches every edge? Which largest set of edges shares no endpoint? Which smallest set of edges touches every vertex? Scheduling, network monitoring, tournament pairing and resource assignment are all one of these four in disguise.

This lesson defines each one, proves how they relate through two short identities, explains the difference between "maximal" and "maximum" (a classic source of confusion), and checks everything by brute force on small graphs. You should be comfortable with graph basics and the bipartite matching idea.

Definitions

Let G be a simple graph with n vertices.

  • An independent set is a set of vertices, no two of which are adjacent. The size of the largest one is the independence number α(G).
  • A vertex cover is a set of vertices such that every edge has at least one endpoint in the set. The smallest size is the vertex cover number β(G).
  • A matching is a set of edges, no two of which share an endpoint. The largest size is the matching number α'(G). A matching that touches every vertex is perfect.
  • An edge cover is a set of edges such that every vertex is an endpoint of at least one of them. It exists only if no vertex is isolated. The smallest size is the edge cover number β'(G).

The pairs (independent set, vertex cover) are about vertices, and (matching, edge cover) are about edges. Notice the symmetry: the first of each pair is a "no conflict" set, and the second is a "covers everything" set.

Two identities

Independent sets and vertex covers are complements. A set S is independent exactly when every edge has at most one endpoint in S, that is, when every edge has at least one endpoint outside S. So S is independent if and only if the rest of the vertices, V \ S, is a vertex cover. Maximizing one minimizes the other:

TEXT
α(G) + β(G) = n

Matchings and edge covers (Gallai's identity). If G has no isolated vertices,

TEXT
α'(G) + β'(G) = n

To see why, take a maximum matching M (covering 2·|M| vertices) and add one extra edge for each of the n - 2|M| uncovered vertices. That edge cover has |M| + n - 2|M| = n - |M| edges. The matching number α' can never exceed β either, because each matching edge needs its own vertex in any cover, giving α'(G) ≤ β(G).

For bipartite graphs, Kőnig's theorem says the inequality is an equality: α'(G) = β(G). That is why bipartite matching reduces to a flow problem and why a minimum vertex cover can be read from a maximum matching.

Python Brute-force the four numbers and check the identities

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In every row α + β = n and μ + ρ = n. The graphs where β differs from the matching number are the odd cycle C5 and K4 (the last column skips them). Neither is bipartite, so Kőnig's theorem does not apply.

Maximal versus maximum

These two words differ and the difference is important.

  • A maximal set cannot be extended by adding anything (it is "stuck").
  • A maximum set has the largest possible size among all sets of that type.

Every maximum set is maximal, but a maximal set can be far smaller than the maximum. A greedy algorithm that picks any available edge and keeps going always finishes with a maximal matching, which may miss the maximum. For example, in the path a-b-c-d, choosing the middle edge b-c leaves nothing else, a matching of size 1, while a-b and c-d form a matching of size 2.

Greedy still has a guarantee: a maximal matching has at least half as many edges as a maximum one. And taking both endpoints of every edge in a maximal matching gives a vertex cover at most twice the optimal size, a classic 2-approximation for the (NP-hard) minimum vertex cover problem. Independent set and vertex cover are NP-hard in general; matching is solvable in polynomial time.

Python Greedy maximal versus maximum matching, and the 2-approximation

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Where these show up

  • Independent set: choose the most meetings that do not conflict; place the most guards or antennas that do not interfere.
  • Vertex cover: place the fewest cameras so that every corridor is watched.
  • Matching: assign workers to jobs, pair students for projects, kidney exchanges.
  • Edge cover: choose the fewest flights or links so that every city is served at least once.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. A graph has 10 vertices and its largest independent set has size 4. What is its minimum vertex cover size?

    An independent set is exactly the complement of a vertex cover, so α + β = n and β = 10 - 4 = 6.
  2. 2. What is the difference between a maximal and a maximum matching?

    Maximal means no edge can be added. Maximum means no matching is larger. A maximal matching can be smaller than the maximum.
  3. 3. A graph on 8 vertices with no isolated vertices has a maximum matching of 3 edges. What is its smallest edge cover?

    By Gallai's identity α' + β' = n, so β' = 8 - 3 = 5.
  4. 4. Kőnig's theorem states that for bipartite graphs the maximum matching size equals...

    In bipartite graphs, the size of a maximum matching equals the size of a minimum vertex cover.
  5. 5. Can a star with one center and 4 leaves have a perfect matching?

    All edges share the center, so a matching holds only one of them and the other three vertices stay uncovered.

Summary

  • An independent set has no edge inside it; a vertex cover touches every edge; a matching has no shared endpoints; an edge cover touches every vertex.
  • α(G) + β(G) = n because independent sets and vertex covers are complements; α'(G) + β'(G) = n (Gallai) when no vertex is isolated.
  • In bipartite graphs the matching number equals the vertex cover number (Kőnig).
  • Maximal means "cannot grow", maximum means "largest possible"; greedy gives maximal matchings and a 2-approximate vertex cover.

Next: Trees and Spanning Trees, where a different kind of subgraph takes the stage.