The degree of a graph vertex of a graph is the number of graph edges which touch . 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 VertexDegree[g], and precomputed vertex degrees are available for particular embeddings of many named graphs via GraphData[graph, "VertexDegrees"].
The minimum vertex degree in a graph is denoted , and the maximum vertex degree is denoted (Skiena 1990, p. 157).
The graph vertex degree of a point in a graph, denoted , satisfies
where 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 . 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 and ) also satisfy the criterion.
Directed graphs have two types of degrees, known as the indegree and the outdegree.