Solution to Show that every simple finite graph has two vertices of the same degree - Sikademy
Author Image

Archangel Macsika

Show that every simple finite graph has two vertices of the same degree

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Assume the graph G has n vertices. The possibilities for the degree are {0,...,n-1}. However, G cannot have one vertex of degree 0 and one vertex of degree n-1, because these two vertices would need to be adjacent to satisfy degree n-1. Using the pigeonhole principle, we must pick the n degrees (one for each vertex), from a set of n-1 answers (since we cannot have both 0 and n-1). Hence, one degree must be repeated.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-657-qpid-542