Graph theory proof

1. Jan 8, 2016

TheMathNoob

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. Jan 8, 2016

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)".

3. Jan 8, 2016

TheMathNoob

mmmm can I use the definition of combinations?

4. Jan 8, 2016

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.

5. Jan 8, 2016

TheMathNoob

Thank you!, so I need induction to prove that it is always n choose 2 for this specific case.

6. Jan 8, 2016

Staff: Mentor

I don't know whether you need it. At least it is short.

7. Jan 8, 2016

TheMathNoob

Yes, anyways I already proved it inductively.

8. Jan 9, 2016

epenguin

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.

9. Jan 9, 2016

TheMathNoob

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?

10. Jan 9, 2016

epenguin

Someone who formulates things in a simple and straightforward unerudite way.

11. Jan 9, 2016

TheMathNoob

I am still trying to learn how to be like that. I agree with you.

12. Jan 12, 2016

epenguin

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!