## Prove that two vertices must have same degree

Math help in Numerical Analysis, Systems of Equations: Cholesky, LU factorization, Consistence, Differential Equations (ODE), Euler's Method, Approximation of Integrals: Simpson's method, Partial Differential Equations (PDE), Symbolic Computations, Latex, Game Theory, Graph Theory; Relations, Equivalence, Implication, Boolean values, True, False, or, and, xor, Predicates, First Order Logic, Second Order Logic, Decidability, Turing machine, P problems, NP problems, Axioms, Axiom of Choice; Paradoxes: Russel, Banach-Tarski; Goedel's Incompleteness Theorem, Foundations of Mathematics on My Math Forum.
Math problems on Numerical Series Geometry Other Topics

### 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
King of Diamonds

Posts: 241
Joined: Sun Sep 20, 2009 1:51 pm

### 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
Joker

Posts: 1519
Joined: Tue Feb 24, 2009 11:00 am

### Re: Prove that two vertices must have same degree

aswoods wrote: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
King of Diamonds

Posts: 241
Joined: Sun Sep 20, 2009 1:51 pm

### 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
Joker

Posts: 1519
Joined: Tue Feb 24, 2009 11:00 am

### Re: Prove that two vertices must have same degree

aswoods wrote: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
King of Diamonds

Posts: 241
Joined: Sun Sep 20, 2009 1:51 pm

Return to Applied Mathematics, Set Theory, Logics and other

### Who is online

Users browsing this forum: No registered users and 4 guests