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!

Graph theory proof

  1. Jan 8, 2016 #1
    1. The problem statement, all variables and given/known data
    Prove that a complete graph with n vertices contains n(n − 1)/2 edges.

    2. Relevant equations


    3. The attempt at a solution
    The solution gives and inductive proof, but I am just wondering if this works as well.

    If we have a set of n vertices or points and we try to match all possible number of vertices, then the final outcome will be a complete a graph. The equation to produce this matching is n choose 2 which equals n(n-1)/2
     
  2. jcsd
  3. Jan 8, 2016 #2

    fresh_42

    Staff: Mentor

    That's correct. But you just transformed the induction to your formula. How do you know it's n choose 2?

    EDIT: The expression "n choose 2" is misleading here because it is to prove that "choosing 2 elements out of n (the doing) has n choose 2 possibilities to do so (the formula)".
     
  4. Jan 8, 2016 #3
    mmmm can I use the definition of combinations?
     
  5. Jan 8, 2016 #4

    fresh_42

    Staff: Mentor

    I thought that were the combinatoric definition. n choose 2 shows up so often that you can probably use dozens of different views. I mean what you wrote is a proof. And induction proves the formula. It presumably can be proven in many ways. Induction is one.
     
  6. Jan 8, 2016 #5
    Thank you!, so I need induction to prove that it is always n choose 2 for this specific case.
     
  7. Jan 8, 2016 #6

    fresh_42

    Staff: Mentor

    I don't know whether you need it. At least it is short.
     
  8. Jan 8, 2016 #7
    Yes, anyways I already proved it inductively.
     
  9. Jan 9, 2016 #8

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    Just be a country boy. No standard combinatorics formula that you will have forgotten or be uncertain about in a few years. You start with n vertices and from each of them to how many other places can you draw an edge? I'll leave you to work out the /2 but you don't need to be God's gift to mathematics for it.
     
  10. Jan 9, 2016 #9
    Hello epenguin, I already proved this by using induction. I just have to use the trick of adding k edges when a new vertex is added to a complete graph. What is a country boy XD?
     
  11. Jan 9, 2016 #10

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    Someone who formulates things in a simple and straightforward unerudite way. :oldsmile:
     
  12. Jan 9, 2016 #11
    I am still trying to learn how to be like that. I agree with you.
     
  13. Jan 12, 2016 #12

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    It sounds like this was your first exposure to induction proofs. If you found them natty and satisfactory far be it from me to put you off. Sometimes induction proofs seem to me not so insightful when you can get a proof without induction. But I guess that's just a personal preference and prejudice. I guess they are particularly natural in graph theory - you construct for instance a graph with certain properties and vertex/edge number and try to add a vertex/edge showing the larger graph has that property.

    You have now given two examples of graph theory statements Jan 5, 2016 and that the only proof I personally would require would be the word 'obviously'. But for all I know that's what your Prof did say, but then required you to prove them after the lesson as an exercise to make sure you understand induction. Don't take any notice of me! :oldbiggrin:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Graph theory proof
  1. Graph Theory Proof (Replies: 1)

Loading...