BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-72-268
       ENTRY:: October 16, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Degrees and matchings.
        TYPE:: Technical Report
      AUTHOR:: Chvatal, Vaclav
        DATE:: March 1972
       PAGES:: 17
    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.
       NOTES:: [Adminitrivia V1/Prg/19951016]
         END:: STAN//CS-TR-72-268