Erdős–Pósa theorem

ID: erdos-posa-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.

New to topics? Read the docs here!