NinaMarmolejo259 NinaMarmolejo259
  • 14-09-2019
  • Mathematics
contestada

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

Respuesta :

steffaniasierrag
steffaniasierrag steffaniasierrag
  • 27-09-2019

Answer:

It isn't possible.

Step-by-step 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.

Answer Link

Otras preguntas

Plz Answer Which event is more likely: rolling a standard number cube and getting an even number, or flipping a coin and having it land heads up?
Which state historically provided the most opportunity and protection for asian immigrants? a.california?
Factors that weaken the competitive pressures created by rivalry among competing sellers include
Odysseus is known for his successful kingdom his prowess as a sailor his humility and manners his strength and intellect
I do not how to solve this please help me
prokaryotic cells do not contain​
Sam and Daniel are playing tag. Sam is originally 40 feet away from Daniel. Sam’s speed is 140 feet per minute; Daniel’s speed is 120 feet per minute. Will Sam
HELP PLEASE 30 PTS!!!!!
Please help me with this and thank you
what is the volume of this pyramid? 7560 cm^3 5040cm^3 2520cm^3 1728cm^3