DEGREE (GRAPH THEORY)

:''This article is about the term "degree" as used in graph theory. For alternate meanings, see degree (mathematics) or degree.''
In graph theory, the 'degree' (or 'valency') of a vertex is the number of edges incident to the vertex. The degree of a vertex $v$ is denoted $deg(v)$.

Contents

Undirected graphs

Directed graphs

Special cases of degree value

Isolated vertex

Leaf vertex

Regular graph

Source

Sink

Eulerian graph

Some theorems

Undirected graphs

For an undirected graph, the degree of a vertex is the number of edges incident to the vertex. This means that each loop is counted twice. This is because each edge has two endpoints and each endpoint adds to the degree.
The graph shown to the right has the following degrees:

Vertex	Degree
1	2
2	3
3	2
4	3
5	3
6	1

Directed graphs

In a directed graph, an edge has two distinct ends: a head (the end with an arrow) and a tail. Each end is counted separately. The sum of head endpoints count toward the 'indegree' and the sum of tail endpoints count toward the 'outdegree'.
The indegree is denoted $deg^+(v)$ and the outdegree as $deg^-(v)$
The image to the right has the following degrees:

Vertex	Indegree	Outdegree
1	0	2
2	2	0
3	2	2
4	1	1

Special cases of degree value

Isolated vertex

If a vertex has a zero degree, it is called an isolated vertex.

Leaf vertex

If a vertex has a unity degree, it is called a leaf. This is fairly common in trees in graph theory and trees in data structures.

Regular graph

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$.

Source

A vertex with $deg^+(v)=0$ is called a 'source'. This name comes from the fact that the node is the origin/source of all of its incident edges. In the image under Directed graphs, vertex 1 is a source node.

Sink

A vertex with $deg^-(v)=0$ is called a 'sink'. Similarly to source nodes, a sink gets its name from the fact that the node is the termination/destination/sink of all of its incident edges. In the image under Directed graphs, vertex 2 is a sink node.

Eulerian graph

An undirected graph is Eulerian if and only if it has either 0 or 2 vertices of odd degree.

Some theorems

The degree sum formula states that, given a graph $G=(V,\; E)$,
:$sum\_\{v\; in\; V\}\; deg(v)\; =\; 2|E|,$
and for a directed graph
:$sum\_\{v\; in\; V\}\; deg^+(v)\; =\; sum\_\{v\; in\; V\}\; deg^-(v)\; =\; |E|$
since each edge is incident to two vertices. The formula implies that in any graph, the number of vertices with odd degree is even.