Degrees and matchings.

[摘要] Let n, b, d be positive integers. D. Hanson proposed to evaluate f(n,b,d), the largest possible number of edges in a graph with n vertices having no vertex of degree greater than d and no set of more than b independent edges. Using the alternating path method, he found partial results in this direction. We complete Hanson's work; our proof technique has a linear programming flavor and uses Berge's matching formula.

[学科分类] 计算机科学（综合）