# Homework Help: Graph theory question

1. Jun 12, 2009

### Anro

1. The problem statement, all variables and given/known data

Hello everyone;
This is the problem that I am working on:

(a) - Show that in every graph there are two vertices of the same degree.

(b) - Determine all graphs with exactly one pair of vertices of equal degree.

2. Relevant equations

None.

3. The attempt at a solution

For part (a) I assumed a graph of order n with the largest possible degree is (n – 1), and the smallest possible degree is zero. Next, I showed that if every vertex in this graph has a different degree than the others, then the vertex with degree (n – 1) will have to be connected to the vertex with degree zero, which is a contradiction.

Part (b) is where I’m stuck; I’ve been looking at graphs with 2, 3, and 4 vertices to see if I can get a certain pattern but I can’t seem to find it. So any help would be appreciated; thanks in advance.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted