Graph Theory Proof

  • Thread starter smiles988
  • Start date
  • #1
6
0
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.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,847
966
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 on Graph Theory Proof

  • Last Post
Replies
22
Views
2K
  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
4
Views
808
  • Last Post
Replies
12
Views
2K
Replies
3
Views
1K
Replies
1
Views
7K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
1
Views
508
  • Last Post
Replies
7
Views
829
  • Last Post
Replies
2
Views
1K
Top