Graph Theory in discrete mathematics Let G be a graph with

George Bray

George Bray

Answered question

2022-06-26

Graph Theory in discrete mathematics
Let G be a graph with order 9 so that the degree of each vertex is either 5 or 6. Prove that there are either at least 5 vertices of degree 6 or at least 6 vertices of degree 5

Answer & Explanation

Paxton James

Paxton James

Beginner2022-06-27Added 25 answers

Step 1
By the Pigeonhole Principle, one of the degree classes has at least 5 members. If that degree class is 6, we're done. So assume there are at least 5 vertices with degree 5. We can't have an odd number of odd degrees, so there must be at least 6 vertices with degree 5.
Step 2
If you're confused by the last statement, the statement "The number of vertices with odd degree is even" is true for any graph. For instance, given any group of people, the number of people who have shaken hands with an odd number of other people in that group is even. This is because each handshake involves two people, so the sum over all people of how many people they've shaken hands with is even. See Number of people having shaken hands an odd number of times
Mayra Berry

Mayra Berry

Beginner2022-06-28Added 7 answers

Step 1
Let the graph have m vertices of degree 6 and n vertices of degree 5.
Then 6 m + 5 n is twice the number of edges and so n is even. If n < 6 then we know n 4.
Step 2
Since m + n = 9, we therefore have m 5.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?