Prove that a smiple graph with at least two vertices would have two or more vertices of the same degree.

thanks.

Printable View

- May 24th 2007, 03:07 PMtttcomraderVertices of a simple graph
Prove that a smiple graph with at least two vertices would have two or more vertices of the same degree.

thanks. - May 24th 2007, 03:41 PMPlato
Realize that if a simple graph has n vertices then the maximum degree of any vertex is n-1. Thus suppose that we have a simple graph G with a degree sequence of <0,1,2,…,n-1>, that is all the n-vertices are of different degree. Now remove the vertex of degree 0. We now have a new graph G’ with (n-1) vertices and the same number of edges. But it has a vertex of degree (n-1). But that is impossible; so the original graph is impossible. Thus the graph G would have to have at least two vertices of the same degree.

- Jun 8th 2007, 01:40 PMfortunaDiscrete maths solutions - option?
TTcommander

Thanks heaps for your explanations.

By the way what is the option of using the "piegonhole" principle of answering the question - 2nd form.

Looking forward to your comments.

Thanks

Fortuna - Jun 8th 2007, 01:49 PMfortunaSorry for getting the name wrong my apology Plato
Plato

By the way what is the option of answering the question using the pigeonhole princple - 2nd form? Look forward to your comments.

Cheers

Fortuna - Jun 8th 2007, 01:49 PMPlato
- Jun 8th 2007, 02:25 PMPlato
Actually the graph theory proof above does use the pigeonhole principle implicitly. Think of 15 pigeonholes numbered 0,1,2,…,14. Assign each person to the hole that matches the number of acquaintances at the meeting that he/she has. If the hole #14 is empty then the fifteen will be assigned to 14 holes so there is a hole 0-13 with at least two. If hole #14 is not empty then someone there knows each other person there. Hence hole #0 must be empty(WHY?) Thus the fifteen will be assigned to 14 holes so there is a hole 1-14 with at least two.

- Jun 8th 2007, 03:37 PMfortunaQuestion 2 - Thanks
Plato

Your explanation makes good sense.

Thanks heaps.

Cheers

Fortuna