Another Proof of the Generalized Tutte—Berge Formula for f‐Bounded Subgraphs

Key Points

• The aim is to establish a new proof of the min-max relation for the size of f-bounded subgraphs using Tutte's theorem.
• Introduced a nonnegative integer weight for each vertex in a multigraph.
• Applied Tutte's f-factor theorem to derive the relation.
• Considered specific conditions where the f-bounded subgraph reduces to classical definitions.
• Confirmed the min-max relation holds for general f-bounded subgraphs.
• Demonstrated that the theory encompasses the classical Tutte-Berge formula for maximum matchings.