Report Number: CS-TR-72-268
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.