My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
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 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.
Singularity is offline  
 
April 17th, 2011, 04:55 AM   #2
 
Joined: Feb 2009
From: Adelaide, Australia

Posts: 1,519
Thanks: 0

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.
aswoods is offline  
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
Singularity is offline  
April 18th, 2011, 02:45 AM   #4
 
Joined: Feb 2009
From: Adelaide, Australia

Posts: 1,519
Thanks: 0

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.
aswoods is offline  
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.
Singularity is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
degree, prove, vertices



Search tags for this page
Click on a term to search for related topics.
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 30-60-90 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





Copyright © 2014 My Math Forum. All rights reserved.