Ask Question
20 September, 18:08

Is it possible for a simple, connected graph that has n vertices all of different degrees? Explain why or why not.

+1
Answers (1)
  1. 20 September, 20:31
    0
    It isn't possible.

    Step-by-step explanation:

    Let G be a graph with n vertices. There are n possible degrees: 0,1, ..., n-1.

    Observe that a graph can not contain a vertice with degree n-1 and a vertice with degree 0 because if one of the vertices has degree n-1 means that this vertice is adjacent to all others vertices, then the other vertices has at least degree 1.

    Then there are n vertices and n-1 possible degrees. By the pigeon principle there are two vertices that have the same degree.
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “Is it possible for a simple, connected graph that has n vertices all of different degrees? Explain why or why not. ...” in 📙 Mathematics if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers