{"id":"palomar/PALOMAR-2026-10-20-000003","url":"https://github.com/jtraverso/erdos-posa-cycles/tree/67bfea6b3893ffdf57e76cd83c9c3538647bdec8","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-10-20-000003-v1.json","repo":"https://github.com/jtraverso/erdos-posa-cycles","tags":["math.CO","msc:05C38","msc:05C70","graph-theory","erdos-posa","formalization"],"score":0,"title":"The Erdős–Pósa theorem for cycles","trust":"high","domain":"math.CO","source":"palomar","authors":["Juan Pablo Traverso Gianini"],"reviews":0,"subject":"math.CO","summary":"A Lean 4 / Mathlib formalization of the Erdős–Pósa theorem: for every k, every finite simple graph either contains k vertex-disjoint cycles or has a set of at most c (k + 1)(log₂(k + 1) + 1) vertices meeting every cycle, for a fixed constant c (the proof gives c = 65); together with the qualitative Erdős–Pósa property and the easy converse that a feedback vertex set of size s rules out s + 1 disjoint cycles. Mathlib has acyclic graphs but not this theorem.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-10-20","reactions":{},"formalized":true,"formalizes":[{"title":"On independent circuits contained in a graph","identifier":"doi:10.4153/CJM-1965-035-8","relationship":"formalizes"}]}