The Erdos-Posa theorem, named for Paul Erdos and Lajos Posa, relates two parameters of a graph: the largest number of vertex-disjoint cycles it contains, and the smallest size of a feedback vertex set, a set of vertices meeting every cycle. The theorem shows these two quantities are related by a function f(k), so a graph with no k vertex-disjoint cycles has a feedback vertex set bounded in terms of k, even though the gap between the two parameters can grow arbitrarily large in particular graphs.
Facts
Classification
Statement Form Connections
Has Statement Form
In Branch
Source Erdos-Posa theorem (Wikipedia)
Proved By
Source Erdos-Posa theorem (Wikipedia)
Sources
1. Erdos-Posa theorem (Wikipedia)
Lead section
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: The size of the largest collection of vertex-disjoint cycles contained in the graph; The size of the smallest feedback vertex set in the graph: a set that contains one vertex from every cycle.
- In Branch: Graph Theory, Lead sentence
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.