5.6k views
1 vote
Is it possible for a simple, connected graph that has n vertices all of different degrees? Explain why or why not.

User Abel D
by
8.3k points

1 Answer

1 vote

Answer:

It isn't possible.

Explanation:

Let G be a graph with n vertices. There are n possible degrees: 0,1,...,n-1.

Observe that a graph can not contain a vertice with degree n-1 and a vertice with degree 0 because if one of the vertices has degree n-1 means that this vertice is adjacent to all others vertices, then the other vertices has at least degree 1.

Then there are n vertices and n-1 possible degrees. By the pigeon principle there are two vertices that have the same degree.

User Gongshw
by
8.4k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.