Editing Degree (graph theory) (section)

==Degree sequence==
[[File:Conjugate-dessins.svg|thumb|200px|Two non-isomorphic graphs with the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1).]]
The '''degree sequence''' of an undirected graph is the non-increasing sequence of its vertex degrees;{{sfnp|Diestel|2005|p=216}} for the above graph it is (5, 3, 3, 2, 2, 1, 0). The degree sequence is a [[graph invariant]], so [[Graph isomorphism|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 simple 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,&nbsp;3,&nbsp;1), cannot be realized as the degree sequence of a graph. The inverse 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 (forming a [[matching (graph theory)|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 be solved by either 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 '''<math>k</math>-graphic''' if it is the degree sequence of some simple <math>k</math>-uniform hypergraph. In particular, a <math>2</math>-graphic sequence is graphic. Deciding if a given sequence is <math>k</math>-graphic is doable in [[Time complexity|polynomial time]] for <math>k=2</math> via the [[Erdős–Gallai theorem]] but is [[NP-completeness|NP-complete]] for all <math>k\ge 3</math>.<ref>{{Cite journal
 | last1 = Deza | first1 = Antoine
 | last2 = Levin | first2 = Asaf
 | last3 = Meesum | first3 = Syed M.
 | last4 = Onn | first4 = Shmuel
 | date = January 2018
 | title = Optimization over Degree Sequences
 | journal = SIAM Journal on Discrete Mathematics
 | language = en
 | volume = 32
 | issue = 3
 | pages = 2067–2079
 | doi = 10.1137/17M1134482
 | issn = 0895-4801
 | arxiv = 1706.03951
 | s2cid = 52039639}}</ref>