ON THE EFFECT OF MAJOR VERTICES ON THE NUMBER OF LIGHT EDGES

This paper presents an inequality satisfied by planar graphs of minimu m degree five. For the purposes of this paper, an edge of a graph is l ight if the weight of the edge, or the sum of the degrees of the verti ces incident with it, is at most eleven. The inequality presented show s that planar graphs of minimum degree five have a large number of lig ht edges. This inequality improves upon a recent inequality of Borodin and Sanders, which showed that 7/15 times the number of edges of weig ht 10 plus 1/5 times the number of edges of weight 11 is at least 12. These constants 7/15 and 1/5 were shown to be best possible. The inequ ality in this paper shows that, for this type of graph, the presence o f vertices of degree at least eight increases the number of light edge s. A graph is presented which shows that the coefficient obtained for the number of degree eight vertices is best possible. (C) 1996 John Wi ley & Sons, Inc.