Graph Theory - degree of vertices in a simple graph

Question

Let $G$ be a simple graph. Either prove there are two vertices of $G$ with the same degree, or find an example where all vertices have a different degree.

So, here is what I thought. A simple graph can be a tree that we can build by increasing by 1 the degree of each vertex compared to everything else. However, I don't know how to express it as an example because we will have a graph that is infinite.

Can anyone help me with that? Or, can someone put the basis for the proof?

Any help is very much appreciated.

Answer 1

Hint: In a simple graph $G=(V, E)$ on $n$ vertices, the maximum degree of a vertex is $n-1$. In particular, the set of possible degrees is $A := \{0, 1, \ldots, n-1\}$, and has cardinality $n$. Now suppose that each vertex in your graph $G$ has a distinct degree. Then we can define an injection $$\phi: V \rightarrow A$$ $$v \mapsto deg(v).$$

But $V$ and $A$ have the same cardinality, so injectivity actually implies ___________.

Now note that the only way for a vertex to have degree $n-1$ is if it is adjacent to all other vertices in the graph. Can you find a contradiction?

Answer 2

Suppose all vertices have different degree. Then all the numbers $0,1,2,...,n-1$ appears as degrees. But then there is a vertex (of degree $n-1$) which is connected to all vertices and including that one with degree $0$. A contradiction.