Maths WorkshopMaths problems with full solutions
Exercise 960Combinatorics › Graph theoryL1Added 3 Nov 2026

A graph with a unique degree sequence

#degree sequence#unique#graph

Statement

Show that the degree sequence (2,2,2,2,2)(2,2,2,2,2) corresponds to the cycle C5C_5 (up to isomorphism).

Hint

A connected 2-regular graph is a cycle.

Show solutionHide solution

Solution

2-regular. Every vertex has exactly 22 neighbors.

Structure. Starting from any vertex, follow one neighbor; each vertex has exactly one other neighbor to continue to, forcing a cycle. Connected 2-regular on 55 vertices = C5C_5.

Conclusion. The only 2-regular graph on 55 vertices is C5C_5.