Degree (graph theory)

(Redirected from Valency (mathematics))

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

$\sum_{v \in V} \deg(v) = 2|E|$

Top Encyclopedia Articles
 Encyclopedia Index animal human sexuality human growth hormone DNA human body human anatomy genetics human cloning human heart human brain human genome project amino acids gene human skeleton

07-14-2008 23:18:10