1. Not finding help here? Sign up for a free 30min 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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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

Have something to add?



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

Loading...