Ask Question
23 January, 14:49

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

+5
Answers (1)
  1. 23 January, 17:21
    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 you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers