Another Proof of the Generalized Tutte—Berge Formula for f‐Bounded Subgraphs
ABSTRACT Given a nonnegative integer weight for each vertex in a multigraph , an ‐bounded subgraph of is a multigraph contained in such that for all . Using Tutte's ‐Factor Theorem, we give a new proof of the min–max relation for the maximum size of an ‐bounded subgraph of . When for all , the formula reduces to the classical Tutte–Berge Formula for the maximum size of a matching.
Authors
- Douglas B. West (ORCID: https://orcid.org/0000-0001-8818-1667)
- Zishen Qu
Institutions
- Zhejiang Normal University (CN)
- University of Illinois Urbana-Champaign (US)
- Illinois College (US)
Publication Details
- Journal
- Journal of Graph Theory
- Published
- 2026-03-16
- DOI
- https://doi.org/10.1002/jgt.70019
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00