Vertex Degree
The degree of a graph vertex 👁 v
of a graph 👁 G
, also called the vertex degree or local degree, is the number
of graph edges which touch 👁 v
. The vertex degrees are illustrated above for a random graph.
The vertex degree is also called the local degree or valency. The ordered list of
vertex degrees in a given graph is called its degree
sequence. A list of vertex degrees of a graph can be computed in the Wolfram
Language using [g],
and precomputed vertex degrees are available for particular embeddings of many named
graphs via [graph,
].
The minimum vertex degree in a graph 👁 G
is denoted 👁 delta(G)
, and the maximum
vertex degree is denoted 👁 Delta(G)
(Skiena 1990, p. 157).
The graph vertex degree of a point 👁 v
in a graph, denoted 👁 rho(v)
, satisfies
where 👁 E
is the total number of graph edges.
In addition, a connected graph nodes satisfies
where the inequality can be made strict except in the case of the singleton graph 👁 K_1
.
However, while this condition is necessary for a graph
to be connected, it is not sufficient;
an arbitrary graph satisfying the above inequality may be connected
or disconnected. In fact, the criterion is
not useful for connectedness testing since almost all disconnected graphs (with the
exception of some disjoint unions of 👁 K_1
and 👁 P_2
) also satisfy the criterion.
Directed graphs have two types of degrees, known as the indegree and the outdegree.
See also
Degree Sequence, Directed Graph, Even Vertex, Graph, Graph Edge, Graph Vertex, Indegree, Maximum Vertex Degree, Minimum Vertex Degree, Odd Vertex, Outdegree, Planted Tree, Vizing's TheoremExplore with Wolfram|Alpha
More things to try:
References
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Referenced on Wolfram|Alpha
Vertex DegreeCite this as:
Weisstein, Eric W. "Vertex Degree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VertexDegree.html