Proof of Degree 5/6 for Graph Theory: Pigeonhole Principle

[smiles988]

1. Suppose a graph has nine vertices each of degree 5 or 6. Prove that at least five vertices have degree 6 or at least six vertices have degree 5.

Homework Equations

3. I'm pretty sure that I need to use the Pigeonhole Principle to solve, but don't know where to go from there.

 

[HallsofIvy]

Suppose the graph has fewer than 5 vertices of degree 6. How many vertices does that leave? What degree do those vertices have?

 

[Architeuthis Dux]

The Pigeonhole Principle is a fundamental principle in combinatorics that states that if there are more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon. In this case, we can think of the vertices as pigeons and the possible degrees (5 or 6) as pigeonholes.

To prove that at least five vertices have degree 6 or at least six vertices have degree 5, we can use a proof by contradiction. Assume that there are less than five vertices with degree 6 and less than six vertices with degree 5. This means that there are at most four vertices with degree 6 and at most five vertices with degree 5.

Since the graph has nine vertices, we can use the Pigeonhole Principle to conclude that at least one of the degrees (5 or 6) must have more than one vertex. Without loss of generality, let's assume that there are at least two vertices with degree 6. This means that there are seven vertices remaining, and at most three of them can have degree 6 (since there can only be a maximum of four vertices with degree 6).

But this would mean that there are at least six vertices with degree 5 (since there are nine vertices in total and at most three of them can have degree 6). This contradicts our initial assumption that there are at most five vertices with degree 5. Therefore, our assumption must be false and the statement is proven.

In conclusion, the Pigeonhole Principle can be used to prove that in a graph with nine vertices, at least five vertices must have degree 6 or at least six vertices must have degree 5. This is an important application of the principle in graph theory.