König’s rank (more commonly called the König number or matching number) refers to the size of the maximum matching in a bipartite graph. It comes from König’s theorem, a foundational result in graph theory proved by Hungarian mathematician Dénes Kőnig. The theorem states that in any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover. This elegant equivalence connects two problems that seem quite different on the surface.
What the Theorem Actually Says
To make sense of König’s rank, you need two concepts. A matching is a set of edges in a graph where no two edges touch the same vertex. Think of it as pairing things up so nothing gets double-assigned. A vertex cover is a set of vertices that touches every edge in the graph, meaning at least one endpoint of every edge is in your chosen set.
König’s theorem says that in a bipartite graph (a graph whose vertices split into two groups, with edges only running between groups), the largest possible matching and the smallest possible vertex cover always have the same size. If you can pair up at most 5 edges without overlap, then you also need exactly 5 vertices to “cover” every edge. This number is König’s rank for that graph.
This equality does not hold for graphs in general. It’s a special property of bipartite graphs, and it’s one of the reasons bipartite structures are so useful in applications like scheduling and resource allocation.
A Simple Example
Imagine you have three workers and three tasks, and each worker can only do certain tasks. You draw a bipartite graph: workers on the left, tasks on the right, and an edge whenever a worker can handle a task. A maximum matching tells you the most worker-task pairs you can make without assigning anyone twice. König’s theorem guarantees that if, say, you can match all three workers to tasks, then any set of vertices covering all the edges must also have exactly three vertices.
This kind of setup appears constantly in real problems. Job assignments, course scheduling, organ donor matching, and network routing all reduce to bipartite matching. König’s rank tells you the capacity of the system: how many simultaneous pairings it can support.
Connection to Matrices
König’s rank also shows up in matrix language. If you represent a bipartite graph as a grid of 0s and 1s (a 1 where an edge exists, 0 where it doesn’t), the maximum matching corresponds to choosing as many 1s as possible such that no two share a row or column. The minimum vertex cover corresponds to the fewest rows and columns needed to contain all the 1s. König’s theorem says these two counts are always equal. This matrix version is sometimes called the “term-rank” of the matrix.
The Hungarian Algorithm
König’s theorem isn’t just a theoretical curiosity. It provides the mathematical backbone for the Hungarian algorithm, one of the most important methods for solving assignment problems. The algorithm works by repeatedly finding and improving matchings in a bipartite graph until no further improvement is possible. At that point, König’s theorem guarantees the result is optimal.
The algorithm operates on the matrix form of the problem. It identifies zero entries (representing feasible or zero-cost assignments), builds a matching among those zeros, and then checks whether the matching is complete. If not, it adjusts the matrix by subtracting and adding constants to rows and columns, creating new zeros to work with. König’s theorem ensures that the minimum number of lines (rows and columns) needed to cover all zeros equals the maximum number of zeros you can select with no two in the same line. This duality drives the algorithm forward until it finds a perfect assignment.
For weighted versions of the problem, where edges have costs or values, the framework extends through what’s known as the König-Egerváry theorem. Instead of simply counting edges and vertices, you work with weighted covers. A weighted cover assigns values to vertices such that the sum of values on any edge’s endpoints is at least as large as the edge’s weight. The optimal matching and optimal cover have the same total value, mirroring the unweighted case.
How Fast Can You Compute It
Finding the maximum matching (and therefore König’s rank) in a bipartite graph is a well-studied computational problem. The classic algorithm by Hopcroft and Karp from 1973 runs in time proportional to the number of edges multiplied by the square root of the number of vertices. For dense graphs with many edges, approaches based on fast matrix multiplication can achieve slightly better performance.
More recent breakthroughs have pushed the boundary further. A 2024 result achieved a running time that scales nearly linearly with the number of edges for sufficiently dense graphs. For practical purposes, though, the Hopcroft-Karp algorithm or the Hungarian method remain the standard tools, and they handle graphs with thousands of vertices comfortably on modern hardware.
Relationship to Hall’s Marriage Theorem
König’s theorem is closely related to another classic result called Hall’s marriage theorem. Hall’s theorem answers a slightly different question: when can every vertex on one side of a bipartite graph be matched? The answer is that a complete matching exists if and only if every subset of vertices on one side has at least as many neighbors on the other side.
It turns out you can prove Hall’s theorem directly from König’s theorem. If the neighborhood condition holds but a complete matching doesn’t exist, König’s theorem forces the minimum vertex cover to be smaller than the number of vertices you’re trying to match. But a cover that small can’t actually cover all the edges without violating the neighborhood condition, creating a contradiction. So the two theorems are logically intertwined, and knowing one gives you the other.
Why It Matters Beyond Math
König’s rank gives you a single number that captures the pairing capacity of any two-sided system. In workforce planning, it tells you the maximum number of simultaneous assignments. In network design, it reveals the bottleneck in routing connections between two sets of nodes. In compiler optimization, it helps allocate registers efficiently.
The deeper insight of König’s theorem is that finding the best matching and finding the smallest bottleneck are the same problem in bipartite systems. Solving one automatically solves the other, which is why this result from 1931 (later published in Kőnig’s landmark 1936 book, the first ever on graph theory) remains central to combinatorial optimization today.