• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Graph Theory Proof

  • Thread starter smiles988
  • Start date
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.



2. 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

Science Advisor
Homework Helper
41,682
864
Suppose the graph has fewer than 5 vertices of degree 6. How many vertices does that leave? What degree do those vertices have?
 

Related Threads for: Graph Theory Proof

  • Posted
Replies
22
Views
2K
  • Posted
Replies
4
Views
651
  • Posted
Replies
11
Views
1K
Replies
3
Views
1K
Replies
12
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top