# Graph Theory in discrete mathematics Let G be a graph with

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
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Paxton James
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
Step 1
Let the graph have m vertices of degree 6 and n vertices of degree 5.
Then $6m+5n$ is twice the number of edges and so n is even. If $n<6$ then we know $n\le 4$.
Step 2
Since $m+n=9$, we therefore have $m\ge 5$.