What question did this study set out to answer?

The aim is to establish a new proof of the min-max relation for the size of f-bounded subgraphs using Tutte's theorem.

March 18, 2026Journal of Graph Theory0 citationsOpen Access

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

ZQZishen QuUniversity of Illinois Urbana-Champaign DWDouglas B. WestZhejiang Normal University

Puntos clave

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.

Resumen

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.

Preguntar a la IA

Me gusta

Guardar

Ver artículo completo