10

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?

James Rettie
  • 103
  • 1
desiigner
  • 167

3 Answers3

20

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.

nonuser
  • 90,026
  • Perhaps it would be better to include that the graph is simple? – Shubham Johri Feb 04 '19 at 18:04
  • Is it necessary to specify "no loops"? – Shufflepants Feb 04 '19 at 22:24
  • Of course. Take a graph with two vertices and one connected to it self. @Shufflepants – nonuser Feb 04 '19 at 22:25
  • 1
    @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. – Shufflepants Feb 04 '19 at 22:32
  • 1
    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}$. – user253751 Feb 05 '19 at 00:02
  • @Shufflepants: In the terminology I'm familiar with, "graph" implies that there are no self-loops and no duplicate edges. (The term "multigraph" is more general.) I can well believe that some people use a terminology where the term "graph" allows self-loops and duplicate edges; if so, it's quite reasonable to answer the question as-is, while still clarifying the terminology by explicitly restricting it to graphs that do not have self-loops or duplicate edges. – ruakh Feb 05 '19 at 03:06
  • Question to @Aqua: if $G$ is simple there there should not be a vertex of degree $0$, so why did you associate a vertex $v_0$ with a degree $d_1=0$? Thank you. – manooooh Dec 01 '19 at 21:23
14

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.

Robert Shore
  • 23,332
1

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$

Christopher King
  • 10,365
  • As noted at https://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." – ruakh Feb 05 '19 at 03:11
  • @ruakh Huh, didn't know that. I edited a disclaimer into my answer. – Christopher King Feb 05 '19 at 03:44