TOPICS
Search

Vertex Degree


VertexDegrees

The degree of a graph vertex v of a graph G 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 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 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

 sum_(i=1)^nrho(v_i)=2E,

where E is the total number of graph edges.

In addition, a connected graph nodes satisfies

 sum_(i=1)^nrho(v_i)>=1/2(n-1),

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, Local Degree, Maximum Vertex Degree, Minimum Vertex Degree, Odd Vertex, Outdegree, Planted Tree, Vizing's Theorem

Explore with Wolfram|Alpha

References

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Referenced on Wolfram|Alpha

Vertex Degree

Cite this as:

Weisstein, Eric W. "Vertex Degree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/VertexDegree.html

Subject classifications