3
$\begingroup$

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.

  • 0
    i was confused when i wrote it and i am not a native english speaker2011-10-11

2 Answers 2

2

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.

  • 1
    i googled it but didint find anything..however this seems true for vertices that do not have loop.2011-10-11
12

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

  • 0
    For completeness - if there is no connected component with more than 1 vertices, than all connected components have exactly 1 vertex, so all vertices have degree 0, and if n > 1 then there will be at least two with equal degree.2017-10-05