- #1

- 30

- 0

please help by exaplaining this question in steps thank much

Show that in a simple graph with at least two vertices there must be

two vertices that have the same degree. use the Pigeonhole principle.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter hyderman
- Start date

- #1

- 30

- 0

please help by exaplaining this question in steps thank much

Show that in a simple graph with at least two vertices there must be

two vertices that have the same degree. use the Pigeonhole principle.

- #2

cristo

Staff Emeritus

Science Advisor

- 8,122

- 74

- #3

HallsofIvy

Science Advisor

Homework Helper

- 41,847

- 969

- #4

- 30

- 0

i know that Each vertices is connected to either 0, 1, 2, ..., n−1 other vertices but i cannot get the whole idea

please help

i

- #5

- 682

- 1

0,1,2...n-1.

however, how can a vertex have zero degree while another vertex have n-1 degree (connecting to ALL other vertices)? contradiction.

- #6

- 682

- 1

let there be n people in a party. Alex is in the party, and he knows that all the other people make different number of handshakes, how many handshakes does Alex make?

this classic handshake problem is closely related to this situation.

- #7

- 30

- 0

please explain more in details

- #8

- 30

- 0

Assume that the graph has n vertices. Each of those vertices is connected to either 0, 1, 2, ..., n−1 other vertices. If any of the vertices is connected to n−1 vertices, then it is connected to all the others, so there cannot be a vertex connected to 0 others. Thus, it is impossible to have a graph with n vertices where one vertex has degree 0 and another has degree n−1. Thus the vertices can have at most n−1 different degrees, but since there are n vertices, at least two must have the same degree.

Share:

- Replies
- 0

- Views
- 1K