Degree (graph theory)

In the mathematical field of graph theory the degree or valency of a vertex v is the number of edges incident to v (with loops being counted twice). We write deg(v) to denote the degree of v.

In a directed graph the indegree of a vertex v is the number of edges terminating at v and the outdegree is the number of edges originating at v. We write deg ⁺ (v) and deg ^- (v) to denote the indegree and outdegree of v.

A vertex with deg(v) = 0 is called isolated. A vertex with deg(v) = 1 is called a leaf. If each vertex of the graph has the same degree k the graph is called a k-regular graph and the graph itself is said to have degree k.

A vertex with deg ⁺ (v) = 0 is called a source and a vertex with deg ^- (v) = 0 is called a sink.

Some theorems

Given a directed graph G for each vertex v of G

deg(v) = deg ⁺ (v) + deg ^- (v)

The number of vertices with odd degree in any graph is even

Given a graph G=(V,E) then