= Erdős–Pósa theorem
{wiki=Erdős–Pósa_theorem}
The Erdős–Pósa theorem is a result in graph theory that deals with the relationship between the presence of certain subgraphs and the presence of certain structures in a graph. Specifically, it provides a relationship between the existence of a set of vertex-disjoint cycles in a graph and the existence of a set of vertices that intersects all these cycles. To state the theorem more formally, it addresses the case of cycles in graphs.
Back to article page