Ask Question
24 July, 22:24

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. 24 July, 22:28
    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?
Find 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 the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers