# Proving that in a simple graph with $n$ vertices, two vertices have the same degree

I want to prove this claim using contradiction:

Let $G$ be a simple graph with $n$ vertices. Prove by contradiction that $G$ has two vertices having the same degree (Consider the vertex of smallest degree and vertex of largest degree).

I think I know where to start. The vertex of the largest degree is $n-1$ in this graph and the smallest is 1. How can I use contradiction to prove the statement above? I studied the proof of this using pigeonhole but I wanna use contradiction this time.

Suppose such a graph existed. Each vertex in the graph can have a degree from 0 to $n-1$ (simple graphs do not forbid a degree-0 vertex, connected graphs do). Since this range spans $n$ values in total and each vertex degree is different, the degrees are distributed one-per-vertex. In particular, there must exist a vertex with degree $n-1$ and one with degree 0.

Now note that the degree-$n-1$ vertex is connected to all other vertices because the graph is simple, including the degree-0 vertex. But the latter is not connected to any vertex, and this induces the contradiction.

Therefore, two vertices in the graph must have the same degree.

• Beat me to it! +1 – Draconis Mar 14 '18 at 0:38

It would really be the same argument turned around a bit. Assume $G$ is a simple graph on $n$ vertices with all vertices having a different degree. The maximum degree of a vertex is $n-1$, so there must be a vertex of degree $0$. If there is a vertex of degree $0$, it is not a simple graph.

Take a graph $$G$$ where all vertices have distinct degrees. So, $$d(1) and $$d(1)>0, d(2)>d(1)>0, \ldots, d(n)>d(n-1)>\ldots>0.$$

Hence we have just one vertex of degree $$\geq n-1$$.

However, in a simple graph with $$n$$ vertices a vertex can have a maximum degree of $$n-1$$. So, $$d(n)=d(n-1)$$. So, our assumption of having all degrees different was wrong and we have a contradiction.

So, in a simple graph $$G$$, we must have at least $$2$$ vertices of the same degree.

• Welcome to Math.SE! Please format you post using MathJax. This page should give you a start at learning how to typeset mathematics here so that your posts say what you want them to, and also look good. – Brian Mar 16 at 16:46
• I'm confused about why you have $d(1)>0$. Could you explain further? – Mauve Mar 16 at 17:04
• We are showing that we want two vertices of the same degree. So, why would we bother to have d(1) = 0 if we are in a simple graph? I think we can just say that we are considering graphs with at least one edge because in a graph of just one vertex this will never apply. – user654759 Mar 17 at 10:38
• There are graphs with at least one edge that also have isolated vertices: for example, consider the graph $•\phantom{==} •—•—• \phantom{==} • \phantom{==} •—•$. So you cannot just omit the 0-degree case. – Mauve Mar 17 at 17:09