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: Graph Theory Proof

  1. Jan 5, 2015 #1
    1. The problem statement, all variables and given/known data
    Prove that all vertices of a complete graph Kn have deg(v) = (n-1)

    2. Relevant equations
    ∑ deg(v) = 2|E|

    |E| = ½(n)(n-1) for Kn

    3. The attempt at a solution
    I may have over thought this but this was my initial path at a formal proof.

    Using the degree sum formula above and the formula for |E| for Kn,

    ∑ deg(v) = 2|E| = n(n-1)

    Kn has n vertices so,

    deg(v1) + deg(v2) + . . . . + deg(vn) (1/n) = (n-1)

    ∴ Each vertex , v, has degree (n-1)

    EDIT: The degree sum formula was mistakenly labeled as the Handshaking lemma.
    Last edited: Jan 5, 2015
  2. jcsd
  3. Jan 5, 2015 #2
    Interesting approach... it feels like you are using more advanced results to try to prove a simpler result, though - and that simpler result was perhaps used to prove the more complex results.

    "A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge"
    ... that should be enough foundation to build your proof on.
  4. Jan 5, 2015 #3


    Staff: Mentor

    The above is incorrect. The 1/n factor is multiplying only the last term, deg(vn. I imagine that you meant this:
    [deg(v1) + deg(v2) + . . . . + deg(vn)] (1/n) = (n-1)

    In any case, what's your justification for dividing by n? It seems to me that this gives you the average number of vertex degrees.
    In a complete graph with n vertices, each vertex must be connected to each other vertex. Thus, each vertex is connected to n - 1 vertices, so for each vertex v, deg(v) = n - 1. I'm not sure if you need to go into any more detail than this.
  5. Jan 5, 2015 #4
    Ah ha! I just saw the degree sum formula and the edge formula for a complete graph and tried connecting the two to get the result I needed. I should have just went back to the definition of a complete graph. Derp!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted