Degree (graph theory)

In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge.

The minimum degree of a graph is denoted by

is the number of vertices in the graph) is a special kind of regular graph where all vertices have the maximum possible degree,

In a signed graph, the number of positive edges connected to the vertex

[2][3] The degree sum formula states that, given a graph

, The formula implies that in any undirected graph, the number of vertices with odd degree is even.

This statement (as well as the degree sum formula) is known as the handshaking lemma.

The latter name comes from a popular mathematical problem, which is to prove that in any group of people, the number of people who have shaken hands with an odd number of other people from the group is even.

[4] The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees;[5] for the above graph it is (5, 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; in some cases, non-isomorphic graphs have the same degree sequence.

(Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.)

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 construction of such a graph is straightforward: connect vertices with odd degrees in pairs (forming a matching), and fill out the remaining even degree counts by self-loops.

The question of whether a given degree sequence can be realized by a simple graph is more challenging.

This problem is also called graph realization problem and can be solved by either the Erdős–Gallai theorem or the Havel–Hakimi algorithm.

The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration.

More generally, the degree sequence of a hypergraph is the non-increasing sequence of its vertex degrees.