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!

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?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Help me with a proof
  1. Help me (Replies: 7)