|
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 <math>\deg(v)<math> 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 <math>\deg^+(v)<math> and <math>\deg^-(v)<math> to denote the indegree and outdegree of v.
A vertex with <math>\deg(v)=0<math> is called isolated. A vertext with <math>\deg(v)=1<math> 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 <math>\deg^+(v)=0<math> is called a source and a vertex with <math>\deg^-(v)=0<math> is called a sink.
Some theorems
Given a directed graph G for each vertex v of G
- <math>\deg(v) = \deg^+(v) + \deg^-(v)<math>
The number of vertices with odd degree in any graph is even
Given a graph G=(V,E) then
- <math>\sum_{v \in V} \deg(v) = 2|E|<math>
|
