# How to prove that at least two vertices have the same degree in any graph? [duplicate]

I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?

• Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
– Shaun
Commented Feb 4, 2019 at 17:56
• Symmetric, simple graphs? Commented Feb 4, 2019 at 17:56
• Commented Feb 4, 2019 at 22:23

Say graph is simple with no loops and that all vertices have different degree $$d_1,d_2,...d_n$$, then $$\{d_1,d_2,...d_n\} = \{0,1,2...,n-1\}$$

So there is a vertex with degree $$n-1$$ and a vertex with degree $$0$$. A contradiction.

• Perhaps it would be better to include that the graph is simple? Commented Feb 4, 2019 at 18:04
• Is it necessary to specify "no loops"? Commented Feb 4, 2019 at 22:24
• Of course. Take a graph with two vertices and one connected to it self. @Shufflepants Commented Feb 4, 2019 at 22:25
• @greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true. Commented Feb 4, 2019 at 22:32
• Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be $\{0, 1, 2..., n-1\}$. Commented Feb 5, 2019 at 0:02

I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.

Assume that a finite graph $$G$$ has $$n$$ vertices. Then each vertex has a degree between $$n-1$$ and $$0$$. But if any vertex has degree $$0$$, then no vertex can have degree $$n-1$$, so it's not possible for the degrees of the graph's vertices to include both $$0$$ and $$n-1$$. Thus, the $$n$$ vertices of the graph can only have $$n-1$$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.

• You are assuming the graph is simple? Commented Feb 4, 2019 at 22:07
• Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph." Commented Feb 4, 2019 at 23:04

EDIT: Graphs are typically defined as being finite. Infinite graphs are a generalization. I did not know this at the time of the post. I will leave this answer up though in case anyone finds it useful.

Here is a counterexample.

Let $$G$$ be a graph on the positive integers where there is an edge from $$x$$ to $$y$$ if $$x < y \le 2x$$. Note that we will ignore the direction of the edges. So $$2$$, for example, is neighbored by $$1$$, $$3$$, and $$4$$.

Let $$j$$ and $$k$$ be distinct positive integers. Without loss of generality assume that $$j < k$$. Note that $$deg(j) = j + \lfloor j/2 \rfloor$$ and $$deg(k) = k + \lfloor k/2 \rfloor$$. We have that

$$j < k$$ $$\lfloor j/2 \rfloor \le \lfloor k/2 \rfloor$$ $$j + \lfloor j/2 \rfloor < k + \lfloor k/2 \rfloor$$ $$deg(j) < deg(k)$$ $$deg(j) \neq deg(k)$$

Therefore, no two different vertices will have the same degree. $$\square$$

• As noted at en.wikipedia.org/wiki/Graph_theory#Definitions, "V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case." Commented Feb 5, 2019 at 3:11
• @ruakh Huh, didn't know that. I edited a disclaimer into my answer. Commented Feb 5, 2019 at 3:44