Math Is Fun Forum

clooneyisagenius

Member

Registered: 2007-03-25

Posts: 56

Questions about a proof. I'm missing something.

Prove that a graph of order n with at least

Edges must be connected.

A graph of order n can be made up of two disjoint components of order k and n-k.  A complete graph of order k has more edges than any other graph of order k and after that the complete graph of order n-k.  Given these two graphs we will construct an edge between the two disjoint sets to make a connected graph of order n.

This gives the inequality (k choose 2) + (n-k choose 2) < [(n-1)(n-2)]/2 + 1 for 1<=k<=n-1. 

The proof goes as follows:
First we notice that the inequality we want to establish is equivalent to (k choose 2)+(n-k choose 2)<= [(n-1)(n-2)]/2

THEN THE PROOF GOES ON.

I'm confused on the bold and italic parts.
Bold: I get where the left side of the inequality comes from but I'm not seeing where the right side comes from.

Italics: Why this inequality? Why does the right side lose the +1?

Any help would be great!

Last edited by clooneyisagenius (2008-04-10 12:15:47)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Questions about a proof. I'm missing something.

The italics come from this general statement: Given integers a and b such that a < b, a <= b -1.

But the proof seems to be deliberately misleading.

This gives the inequality

But it doesn't give that inequality.  Certainly you wish it to be true for the proof to hold.  But that doesn't make it so.

If you can show that inequality true, then you have a disconnected graph which is made up by two complete graphs.  Also, this graph has at most (n-1)(n-2)/2 edges in it.  Thus, to meet the requirements of the theorem, you must add at least 1 edge.  But the only way to add an edge is between the two compete graphs, making the graph connected.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Questions about a proof. I'm missing something.

This is how I would do the proof:

Label a vertex p.  Pick an arbitrary point in a graph of order n, and add edges between it and every other vertex, except p.  Note that you have just added n-2 edges.  Repeating this for another point, you add n-3, then n-4, and so on.  Go until the graph is complete, excluding p.  There are:

Edges in this graph.  Now to meet the requirements of the theorem, we must add one more edge.  But the only way we can do that is to add an edge connecting p.  Therefore, G is connected.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."