Erdős–Pósa theorem

For every positive integer k, a graph either contains k pairwise vertex-disjoint cycles or has a vertex set of size O(k log k) meeting every cycle. It establishes a bounded trade-off between packing cycles and covering them with vertices.

Connect

Vertex-disjoint cycles: Cycles in a graph whose vertex sets are pairwise disjoint. The packing alternative asks whether the graph contains k cycles with this property.
Paul Erdős: A Hungarian mathematician known for major contributions to combinatorics, number theory, and probability. He co-authored the theorem establishing the cycle packing-covering relation.
Feedback vertex set problem: The optimization problem of finding the smallest vertex set whose deletion makes a graph acyclic. The theorem bounds the size of a cycle-hitting set whenever the cycle packing number is small.
Linear Erdős–Pósa property: An Erdős–Pósa property in which a packing of size k guarantees a transversal of size at most a constant times k. For cycles in general graphs, the classical bound is O(k log k), rather than linear in k.
Erdős–Pósa function: The smallest bound relating packing and transversal numbers for a graph family, as a function of packing size. For cycles in general graphs, its growth is Θ(k log k).
Feedback vertex set: A set of vertices whose deletion leaves a graph with no cycles. A set meeting every cycle is exactly a feedback vertex set.
Lajos Pósa: A Hungarian mathematician whose work includes influential results in graph theory. He co-authored the theorem with Paul Erdős.
Parameterized complexity: The study of computational problems measured by a parameter in addition to input size. Cycle packing and feedback vertex set are often studied with their solution size as the parameter.
Planar graph: A graph that can be drawn in the plane without edge crossings. Cycles in planar graphs have stronger linear packing-covering bounds than arbitrary graphs.
Treewidth: A measure of how closely a graph resembles a tree, defined through tree decompositions. Structural graph parameters can characterize or control packing-covering behavior in graph families.