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
