Erdős–Pósa theorem

In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, relates two parameters of a graph: In many applications, we are interested in finding a minimum feedback vertex set in a graph: a small set that includes one vertex from every cycle, or, equivalently, a small set of vertices whose removal destroys all cycles.

This is a hard computational problem; if we are not able to solve it exactly, we can instead try to find lower and upper bounds on the size of the minimum feedback vertex set.

Any minimum feedback vertex set in the graph in Figure 1 has three vertices: for example, the three vertices A, C, and G. It is possible to construct examples in which the gap between the two quantities - the size of the largest collection of vertex-disjoint cycles, and the size of the smallest feedback vertex set - is arbitrarily large.

For the purpose of discussing bounds on how large f(k) needs to be, we define the Erdős–Pósa function to give, for each positive integer k, the least value of f(k) for which the statement of the theorem holds.

A previous unpublished result of Béla Bollobás stated f(2) = 3: in simpler terms, any graph which does not contain two vertex-disjoint cycles has a feedback vertex set of at most three vertices.

The result that f(2) = 3 was first published by Lovász (1965), who also gave a complete characterization of the case k = 2: that is, he described the graphs which, like the example of K5 given above, do not contain two vertex-disjoint cycles.

not depending on G. Rephrased in this terminology, the Erdős–Pósa theorem states that the family F consisting of all cycles has the Erdős–Pósa property, with bounding function f(k) = Θ(k log k).

As a corollary of their grid minor theorem, Robertson and Seymour proved that F(H) has the Erdős–Pósa property if and only if H is a planar graph.