My Math Forum Prove that two vertices must have same degree

 Applied Math Applied Math Forum

 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 n-vertex 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: 3 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 n-1. But if that maximum is achieved by one vertex, no other vertex has degree zero. Therefore the set of degrees has no more than n-1 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:
 Originally Posted by aswoods 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 n-1. But if that maximum is achieved by one vertex, no other vertex has degree zero. Therefore the set of degrees has no more than n-1 members, which must be assigned to n vertices.
Hi aswoods. We have not learned about non-simple graphs yet. I had considered your argument (basically, the pigeonhole principle). But can a simple graph have a vertex with degree 0? If so, is it still considered part of the graph? If yes to that, then the set of degrees has n members (0, 1, ... n-1).
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: 3 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:
 Originally Posted by aswoods If no vertex has degree zero, the pigeonhole principle takes care of it straight away. Otherwise, use the proof I just gave.
OK, I just reread your proof. I misunderstood it the first time. THx.

 Tags degree, prove, vertices

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# simple graph max degree

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post bilano99 Algebra 2 August 16th, 2012 10:18 AM wrongnmbr Algebra 3 August 16th, 2010 10:02 AM ngm Algebra 1 December 8th, 2009 01:28 AM TimmyTimTim Abstract Algebra 0 March 18th, 2008 07:11 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top