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.
How to find whether it is possible for each vertex of a graph to have a different degree?
3
$\begingroup$
graph-theory
discrete-mathematics
-
0i was confused when i wrote it and i am not a native english speaker – 2011-10-11
2 Answers
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.
-
1i 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.
-
0For 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