Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help me with a proof

  1. Apr 7, 2005 #1
    Help me with a proof!!!

    Suppose that [tex]G[/tex] is a graph with [tex]v[/tex] vertices and [tex]e[/tex] edges and that the degree of each vertex is at least [tex]d_{min}[/tex] and at most [tex]d_{max}[/tex]. Show that:

    [tex]\dfrac{1}{2}d_{min}\ \cdot\ v \ \leq \ e \ \leq \ \dfrac{1}{2}d_{max}\ \cdot\ v [/tex]

    I don't have an idea of where to start on this problem. Thank you for your help!
    Last edited: Apr 7, 2005
  2. jcsd
  3. Apr 7, 2005 #2


    User Avatar
    Science Advisor

    Every edge connects 2 vertices. Suppose every edge had degree exactly dmin. How many edges would there be?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook