Degree (graph theory)

From Wikipedia, the free encyclopedia

A graph with vertices labeled by degree
A graph with vertices labeled by degree

In graph theory, the degree (or valency) of a vertex is the number of edges incident to the vertex.[1] The degree of a vertex v is denoted deg(v). The maximum degree of a graph G, denoted by Δ(G), is the maximum degree of its vertices, and the minimum degree of a graph, denoted by δ(G), is the minimum degree of its vertices. In the graph on the right, the maximum degree is 3 and the minimum degree is 0. In a regular graph, all degrees are the same, and so we can speak of the degree of the graph.


Contents

[edit] Undirected graphs

For an undirected graph, the degree of a vertex is the number of edges adjacent 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 degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees;[2] for the above graph it is (3, 3, 3, 2, 2, 1, 0). The degree sequence is a graph invariant so isomorphic graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; non-isomorphic graphs may have the same degree sequence.

The degree sum formula (also known as "the Handshaking Theorem") states that, given a graph G = (V,E),

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

This may be seen as a form of double counting, in which we count the number of edge-vertex incidences by summing over vertices on the left hand side, and by summing over edges on the right hand side. The formula implies that in any graph, the number of vertices with odd degree is even.

As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a graph. The construction of such a graph is simple: connect odd vertices in pairs, and fill with self-loops.

Often one wishes to search for simple graphs, making the degree sequence problem more challenging. Obviously the sequence (8, 4) is not the degree sequence of a simple graph, since we would have the contradiction Δ(G) > (the number of vertices - 1). The sequence (3, 3, 3, 1) is also not the degree sequence of a simple graph, but in this case the reason is less obvious. Finding general criteria for degree sequences of simple graphs is a classical problem; solutions have been offered by Erdős and Gallai (1960), Havel (1955) and Hakimi (1961), Choudum S. A and Sierksma et al. (1991).

[edit] Directed graphs

A directed graph with vertices labeled (indegree, outdegree)
A directed graph with vertices labeled (indegree, outdegree)

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). A vertex with deg − (v) = 0 is called a source, as it is the origin of each of its incident edges. Similarly, a vertex with deg + (v) = 0 is called a sink.

The degree sum formula states that, for a directed graph

\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |E|\, .

[edit] Special values

An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12
An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12
  • A vertex with degree 0 is called an isolated vertex.
  • A vertex with degree 1 is called a leaf vertex and the edge connected to that vertex is called a pendant edge. In the graph on the right, {3,5} is a pendant edge. This terminology is common in the study of trees in graph theory and especially trees as data structures.

[edit] Global properties

  • 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.
  • An undirected, connected graph has an Eulerian path if and only if it has either either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path can be extended to an Eulerian circuit.
  • A directed graph is a pseudoforest if and only if every vertex has outdegree at most 1. A functional graph is a special case of a pseudoforest in which every vertex has outdegree exactly 1.

[edit] References

  1. ^ Diestel p.5
  2. ^ Diestel p.278