page_title: Degree (graph theory)
section_title: Degree sequence
hierarchical_section_title: Degree (graph theory) / Degree sequence
context_page_description: In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or. The maximum degree of a graph, denoted by, and the minimum degree of a graph, denoted by, are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0.
  In a regular graph, every vertex has the same degree, and so we can speak of the degree of the graph. A complete graph is a special kind of regular graph where all vertices have the maximum degree.
context_section_description: The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees; for the above graph it is (5, 3, 3, 2, 2, 1, 0). The degree sequence is a graph invariant so isomorphic graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs have the same degree sequence.
  The degree sequence problem  is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a matching, and fill out the remaining even degree counts by self-loops.
  The question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is also called graph realization problem and can either be solved by the Erdős–Gallai theorem or the Havel–Hakimi algorithm. 
  The problem of finding or estimating the  number of graphs with a given degree sequence is a problem from the field of graph enumeration.
  More generally, the degree sequence of a hypergraph is the non-increasing sequence of its vertex degrees. A sequence is -graphic if it is the degree sequence of some -uniform hypergraph. In particular, a -graphic sequence is graphic. Deciding if a given sequence is -graphic is doable in polynomial time for  via the Erdős–Gallai theorem but is NP-complete for all  (Deza et al., 2018 ).
caption: Two non-isomorphic graphs with the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1).