Order the steps to show that in a simple graph with at least two vertices there

Question

Order the steps to show that in a simple graph with at least two vertices there must be two vertices that have the same degree. It is impossible for there to be both an i with vi 0 and aj with vj = n-1 since if one vertex is connected to every other, then no vertex can be connected to no other vertex. Step 1 The degree of a vertex, vi, has possible values 0,1. n 1, where n z 2 is the number of vertices in the graph. Step 2 The degree of each of the n vertices comes from a set of at most n 1 elements and hence two must not have the same degree. The degree of each of the n vertices comes from a set of at most n 1 elements and hence at least two must have the same degree. Step 3 It is possible for there to be both an i with vi 0 and a j with vj n 1 since if one vertex is connected to every other, then a vertex can be connected to another other vertex.

Explanation / Answer

Solution:

STEP I: The degree of a vertex, vi, has possible values 0,1,2,...,n-1, where n>=2 is the number of vertices in the graph.

STEP II: It is impossible for there to be both an i with vi=0 and a j with vj=n-1 since if one vertex is connected to every other than no vertex can be connected to no other vertex.

STEP III: The degree of each of the n vertices comes from a set of at most n-1 elements and hence at least two must have the same degree.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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