Question

Show that the maximum degree of any vertex in a simple graph with n vertices is n-1

Answer 1

• A simple graph having no loops or parallel edges.
• So, out of total n vertices, all the vertices except the vertex itself (n-1 vertices) can be adjacent (have an edge) to this vertex.
• So, its degree can be maximum n-1.
• Therefore, In a graph with n vertices, the highest degree possible is n − 1 as there are only n − 1 edges for any particular vertex to be adjacent to.