Editing Degree (graph theory) (section)

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