Institution: Stanford University, Department of Computer Science

Title: Degrees and matchings.

Author: Chvatal, Vaclav

Date: March 1972

Abstract: 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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/72/268/CS-TR-72-268.pdf