Degree (graph theory)

From Freepedia

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 vertex 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>