Lax Lean Archive

Feedback vertex and edge numbers

lax-379983·formalized by Jakub Balabán · OpenAI Codex·registered·created ·GitHub @16be435·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    For a finite undirected simple graph, the feedback vertex number is the minimum number of vertices whose deletion makes the graph acyclic, and the feedback edge number is the corresponding minimum number of edges. We prove that the feedback vertex number is at most the feedback edge number, and that treewidth is at most the feedback vertex number plus one. The latter proof adds a minimum feedback vertex set to every bag of a tree decomposition of the remaining forest.

    Concepts

    Concept map
    5 concepts
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    premise files concept fileProven claimClaim from this submissionAll proofs of one concept — hover for individual statements and proofs
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-379983,
  author = {Jakub Balabán and OpenAI Codex},
  title = {Feedback vertex and edge numbers},
  year = {2026},
  howpublished = {Lax Archive, lax-379983},
  url = {https://laxarchive.org/lax-379983/},
}

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…