Editing Degree (graph theory)

{{Short description|Number of edges touching a vertex in a graph}}
[[File:UndirectedDegrees (Loop).svg|thumb|A graph with a loop having vertices labeled by degree]]

In [[graph theory]], the '''degree''' (or '''valency''') of a [[vertex (graph theory)|vertex]] of a [[Graph (discrete mathematics)|graph]] is the number of [[edge (graph theory)|edges]] that are [[incidence (graph)|incident]] to the vertex; in a [[multigraph]], a [[loop (graph theory)|loop]] contributes 2 to a vertex's degree, for the two ends of the edge.<ref>{{cite book
 | last1 = Diestel | first1 = Reinhard
 | title = Graph Theory
 | url = https://diestel-graph-theory.com/index.html
 | publisher = Springer-Verlag
 | location = Berlin, New York
 | edition = 3rd
 | isbn = 978-3-540-26183-4
 | year = 2005
 | pages = 5, 28}}</ref> The degree of a vertex <math>v</math> is denoted <math>\deg(v)</math> or <math>\deg v</math>. The '''maximum degree''' of a graph <math>G</math> is denoted by <math>\Delta(G)</math>, and is the maximum of <math>G</math>'s vertices' degrees. The '''minimum degree''' of a graph is denoted by <math>\delta(G)</math>, and is the minimum of <math>G</math>'s vertices' degrees. In the multigraph shown 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]] (denoted <math>K_n</math>, where <math>n</math> is the number of vertices in the graph) is a special kind of regular graph where all vertices have the maximum possible degree, <math>n-1</math>.

In a [[signed graph]], the number of positive edges connected to the vertex <math>v</math> is called '''positive deg'''<math>(v)</math> and the number of connected negative edges is entitled '''negative deg'''<math>(v)</math>.<ref name="10.1016/j.physa.2014.11.062">{{cite journal
 | last1 = Ciotti | first1 = Valerio
 | last2 = Bianconi | first2 = Giestra
 | last3 = Capocci | first3 = Andrea
 | last4 = Colaiori | first4 = Francesca
 | last5 = Panzarasa | first5 = Pietro
 | title = Degree correlations in signed social networks
 | journal = Physica A: Statistical Mechanics and Its Applications
 | date = 2015
 | volume = 422
 | pages = 25–39
 | doi = 10.1016/j.physa.2014.11.062
 | url = https://www.sciencedirect.com/science/article/abs/pii/S0378437114010334
 | arxiv = 1412.1024
 | bibcode = 2015PhyA..422...25C
 | s2cid = 4995458
 | access-date = 2021-02-10
 | archive-date = 2021-10-02
 | archive-url = https://web.archive.org/web/20211002175332/https://www.sciencedirect.com/science/article/abs/pii/S0378437114010334 | url-status = live }}</ref><ref>{{cite journal
 | last1 = Saberi | first1 = Majerid
 | last2 = Khosrowabadi | first2 = Reza
 | last3 = Khatibi | first3 = Ali
 | last4 = Misic | first4 = Bratislav
 | last5 = Jafari | first5 = Gholamreza
 | title = Topological impact of negative links on the stability of resting-state brain network
 | journal = Scientific Reports
 | date = January 2021
 | volume = 11
 | issue = 1
 | page = 2176
 | pmid = 33500525
 | pmc = 7838299
 | doi = 10.1038/s41598-021-81767-7
 | bibcode = 2021NatSR..11.2176S
 | url = }}</ref>

==Handshaking lemma==
{{main|Handshaking lemma}}
The '''degree sum formula''' states that, given a graph <math>G=(V, E)</math>,

:<math>\sum_{v \in V} \deg(v) = 2|E|\, </math>.

The formula implies that in any undirected graph, the number of vertices with odd degree is even. This statement (as well as the degree  sum formula) is known as the [[handshaking lemma]]. The latter name comes from a popular mathematical problem, which is to prove that in any group of people, the number of people who have shaken hands with an odd number of other people from the group is even.<ref>{{cite book
| last = Grossman | first = Peter
| title = Discrete Mathematics for Computing
| year = 2009
| url = https://books.google.com/books?id=K5lGEAAAQBAJ&pg=PA185
| page = 185
| publisher = [[Bloomsbury Publishing|Bloomsbury]]
| isbn = 978-0-230-21611-2
}}</ref>

==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>

==Special values==
[[File:Depth-first-tree.png|thumb|An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12]]
*A vertex with degree 0 is called an [[isolated vertex]].
*A vertex with degree 1 is called a leaf vertex or end vertex or a pendant vertex, and the edge incident with that vertex is called a pendant edge. In the graph on the right, {3,5} is a pendant edge. This terminology is common in the study of [[tree (graph theory)|tree]]s in graph theory and especially [[tree (data structure)|tree]]s as [[data structure]]s.
* A vertex with degree ''n''&nbsp;&minus;&nbsp;1  in a graph on ''n'' vertices is called a [[dominating vertex]].

==Global properties==
*If each vertex of the graph has the same degree&nbsp;''k'', the graph is called a [[regular graph|''k''-regular graph]] and the graph itself is said to have degree&nbsp;''k''. Similarly, a [[bipartite graph]] in which every two vertices on the same side of the bipartition as each other have the same degree is called a [[biregular graph]].
*An undirected, connected graph has an [[Eulerian path]] if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit.
*A directed graph is a [[directed pseudoforest]] if and only if every vertex has outdegree at most&nbsp;1. A [[functional graph]] is a special case of a pseudoforest in which every vertex has outdegree exactly&nbsp;1.
*By [[Brooks' theorem]], any graph ''G'' other than a clique or an odd cycle has [[chromatic number]] at most&nbsp;Δ(''G''), and by [[Vizing's theorem]] any graph has [[chromatic index]] at most Δ(''G'')&nbsp;+&nbsp;1.
*A [[Degeneracy (graph theory)|''k''-degenerate graph]] is a graph in which each subgraph has a vertex of degree at most ''k''.

==See also==
*[[Indegree]], [[outdegree]] for [[digraph (mathematics)|digraph]]s
*[[Degree distribution]]
*[[bipartite graph#Degree|Degree sequence for bipartite graphs]]

==Notes==
{{reflist}}

==References==
*{{cite journal|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=T.|last2=Gallai|author2-link=Tibor Gallai|title=Gráfok előírt fokszámú pontokkal|language=hu|journal=Matematikai Lapok|volume=11|year=1960|pages=264&ndash;274|url=http://www.renyi.hu/~p_erdos/1961-05.pdf}}.
*{{cite journal
| last= Havel
| first= Václav
| author-link =V. J. Havel
| year = 1955
| title = A remark on the existence of finite graphs
| language = cs
| journal = Časopis Pro Pěstování Matematiky
| volume = 80
| issue= 4
| pages = 477–480
| doi= 10.21136/CPM.1955.108220
| url = http://eudml.org/doc/19050
| doi-access = free
}}
*{{cite journal
 | last = Hakimi | first = S. L. | author-link = S. L. Hakimi
 | journal = Journal of the Society for Industrial and Applied Mathematics
 | mr = 0148049
 | pages = 496–506
 | title = On realizability of a set of integers as degrees of the vertices of a linear graph. I
 | volume = 10
 | year = 1962| issue = 3 | doi = 10.1137/0110037 }}.
*{{cite journal
 | last1 = Sierksma | first1 = Gerard
 | last2 = Hoogeveen | first2 = Han
 | doi = 10.1002/jgt.3190150209
 | issue = 2
 | journal = [[Journal of Graph Theory]]
 | mr = 1106533
 | pages = 223–231
 | title = Seven criteria for integer sequences being graphic
 | volume = 15
 | year = 1991| url = https://ir.cwi.nl/pub/1579
 }}.

[[Category:Graph theory]]