
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
April 17th, 2011, 01:59 AM  #1 
Senior Member Joined: Sep 2009 Posts: 251 Thanks: 0  Prove that two vertices must have same degree
What strategy do I use to "Prove that in any graph with more than one vertex, there must be two vertices of the same degree"? A direct proof seems out of the question. I tried proof by contradiction, but cannot figure out how to disprove that there is a set which does not have two vertices of the same degree. I tried induction. I proved that for a graph with 2 vertices, they both have degree 0 or 1. I even proved it for a 3 vertex graph (just to see how the induction step might go), but I cannot seem to prove it for n+1 vertices (assuming it's true for nvertex graph). I tried proof by smallest counter example. I successfully showed that n=2 is not a counterexample (no, really, I did!), but had no idea where to go from there. Now I'm out of ideas. What's the trick here? The only theorem on graphs up to this point of the book is that the sum of the degrees of all the vertices in the graph is 2 times the number of edges. Thanks. 
April 17th, 2011, 04:55 AM  #2 
Senior Member Joined: Feb 2009 From: Adelaide, Australia Posts: 1,519 Thanks: 2  Re: Prove that two vertices must have same degree
You have to assume these are "simple" graphs, i.e. a vertex cannot be joined to itself, and cannot be joined to another vertex more than once. Then if there are n vertices, the maximum degree of any vertex is n1. But if that maximum is achieved by one vertex, no other vertex has degree zero. Therefore the set of degrees has no more than n1 members, which must be assigned to n vertices. 
April 17th, 2011, 08:05 PM  #3  
Senior Member Joined: Sep 2009 Posts: 251 Thanks: 0  Re: Prove that two vertices must have same degree Quote:
Edit: My book does allow a vertex in a graph which has no adjacent vertices (that is, the vertex has degree 0). Thanks, Jeff  
April 18th, 2011, 02:45 AM  #4 
Senior Member Joined: Feb 2009 From: Adelaide, Australia Posts: 1,519 Thanks: 2  Re: Prove that two vertices must have same degree
If no vertex has degree zero, the pigeonhole principle takes care of it straight away. Otherwise, use the proof I just gave.

April 18th, 2011, 07:37 AM  #5  
Senior Member Joined: Sep 2009 Posts: 251 Thanks: 0  Re: Prove that two vertices must have same degree Quote:
 

Tags 
degree, prove, vertices 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Vertices of a Triangle  bilano99  Algebra  2  August 16th, 2012 10:18 AM 
Vertices of a triangle?  wrongnmbr  Algebra  3  August 16th, 2010 10:02 AM 
prove that in a 306090 degree triangle, the hypotenuse is  ngm  Algebra  1  December 8th, 2009 02:28 AM 
Prove Existence of Unique monic polynomial of minimal degree  TimmyTimTim  Abstract Algebra  0  March 18th, 2008 07:11 PM 