Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite
1

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|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 – Parhs Oct 11 '11 at 19:23

2 Answers

up vote 2 down vote accepted

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

http://www.student.math.uwaterloo.ca/~math239/winter2008/t7sol.pdf

http://www.mymathforum.com/viewtopic.php?f=27&t=20418

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

share|improve this answer
1  
i googled it but didint find anything..however this seems true for vertices that do not have loop. – Parhs Oct 11 '11 at 15:01
up vote 8 down vote

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|improve this answer
thank you ,this was the example i was thinking of! – Parhs Oct 11 '11 at 15:53

Your Answer

 
discard

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.