Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to prove whether it is possible for a graph to have different degrees for each vertex. I think that it can be possible with an example, but I can't prove it with mathematics.

share|cite|improve this question
Yes it is possible. Consider a graph with zero or one vertex. – LostInMath Oct 11 '11 at 14:49
Please notice that the singular is "vertex" and the plural is "vertices". I changed "vertice" to "vertex" in the question. – Michael Hardy Oct 11 '11 at 15:55
i was confused when i wrote it and i am not a native english speaker – GorillaApe Oct 11 '11 at 19:23
up vote 2 down vote accepted

Every simple graph with at least two vertices has at least two vertices of the same degree.

This was among the first result when searching for "two vertices" "same degree". You can also find many books containing this claim.

share|cite|improve this answer
i googled it but didint find anything..however this seems true for vertices that do not have loop. – GorillaApe Oct 11 '11 at 15:01

If you are talking of simple graphs then clearly in any connected component containing n(>1) vertices the n vertex degrees will have degrees among the numbers $\{1,2,3\cdots n-1\}$ and so by the pigeonhole principle at least 2 vertices will have the same degree. The conclusion is false if we consider graphs with loops or with multiple edges. enter image description here

share|cite|improve this answer
thank you ,this was the example i was thinking of! – GorillaApe Oct 11 '11 at 15:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.