In any finite graph with at least two vertices, there must be two vertices with the same degree

Show that, in any finite graph with at least two vertices, there must be two vertices with the same degree.

HINTS ONLY!

Solution 1:

Hint: Suppose the graph has $n$ vertices. Which integers can be the degree of a vertex?

Solution 2:

Degree of a vertex can range from $1$ to $n-1$ and the number of vertices is $n$. Hence according to the pigeon hole principle at least $2$ vertices will have the same degree.

Solution 3:

You could assume that every vertex of $G$ has a unique degree and produce a contradiction. That is, since $G$ has order $n$ and every vertex degree is unique we know that the possible degree values must be $0,1,...,n-1$.

You could also use the pigeonhole principle since you know that $G$ either has a vertex of degree $n-1$ or it does not (two cases). With this information you can figure out the relationship between the number of vertices in $G$ and the set of all possible degrees for a vertex in $G$.

Does every number not ending with zero have a multiple without zero digits at all?

How to explain why the probability of a continuous random variable at a specific value is 0?

If $(a_n)$ is increasing and $\lim_{n\to\infty}\frac{a_{n+1}}{a_1\dotsb a_n}=+\infty$ then $\sum\limits_{n=1}^\infty\frac1{a_n}$ is irrational

Block inverse of symmetric matrices

Solution of $ax=a^x$

Continuous partials at a point without being defined throughout a neighborhood and not differentiable there?

What is the proper geometrical name for a a rectangle with a semi-circle at each end?

Does the sum of the reciprocals of composites that are $ \le $ 1

What's the limit of $\prod_1^\infty \left(1-\frac{1}{2^n}\right)=(1-1/2)(1-1/4)(1-1/8)...$?

The category Set seems more prominent/important than the category Rel. Why is this?

Quotient of a Lie algebra by a subalgebra - what is it?

"Reciprocal" of derivatives