Employ the pigeon hole principle to prove the following: Claim: Let G be an undi

Question

Employ the pigeon hole principle to prove the following: Claim: Let G be an undirected graph with at least two vertices. Then there exist distinct vertices v and w in G that have the same degree. I have written this out a few ways. I am just not sure if I am doing it right. Do they have the same degree because if there are two vertices with n+1 edges in an undirected graph, then both vertices are considered to be degree 3? it may be obvious, but I need some clarification.

Explanation / Answer

In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item. This theorem is exemplified in real-life by truisms like "there must be at least two left gloves or two right gloves in a group of three gloves". It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results; for example, that two people in London have the same number of hairs on their heads

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.