1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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