Does Induction Work for Proving Graph Theory Statements?

[TheMathNoob]

Homework Statement

Prove that a complete graph with n vertices contains n(n − 1)/2 edges.

Homework Equations

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

 

[fresh_42]

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

 

[TheMathNoob]

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

mmmm can I use the definition of combinations?

 

[fresh_42]

mmmm can I use the definition of combinations?

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.

 

[TheMathNoob]

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.

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

 

[fresh_42]

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

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

 

[TheMathNoob]

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

Yes, anyways I already proved it inductively.

 

[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.

 

[TheMathNoob]

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.

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?

 

[epenguin]

What is a country boy XD?

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

 

[TheMathNoob]

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

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

 

[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!