Degree (graph theory)

from Wikipedia, the free encyclopedia

Degree (also knot degree or valence ) is a fundamental term in graph theory , a branch of mathematics . The degree of a node is the number of edges that are adjacent to it.


Undirected graph

An undirected graph. The nodes are labeled with their degree.

In an undirected graph , the degree for each node is defined as the number of all edges of which are adjacent to. If there are any loops, they are counted twice.

Instead is often the notation used. The index can be omitted if it is clear which graph it is.

The smallest degree of a node in is called the minimum degree of and is called the , the highest degree of a node in is called the maximum degree of , this is usually called. The average of all nodes degrees of will average grade called and called.

Directed graph

A directed graph with labeled nodes: (degree of entry, degree of exit)

A directed graph distinguishes whether an edge begins or ends at a node . With denotes the degree of entry of the node in a directed graph and its degree of exit .

Here is the number of all edges that end in and the number of all edges that start in.

A node without input edges ( ) is called a source , a node without output edges ( ) is called a sink .

Related terms

  • A node is said to be isolated if it:
    • in an undirected graph : has no neighbors .
    • in a directed graph : has no predecessors and no successors. .
  • An undirected graph or hypergraph is called regular if all of its nodes have the same degree. Have all of its nodes degree , it is referred as a regularly-k . A 3-regular graph is also called cubic .
  • A directed graph is called regular if all of its nodes have the same degree of entry and exit. Possess all its node input and output level so is referred to as regular-k .
  • A hypergraph is called uniform if all edges of contain the same number of nodes. If all edges of exactly contain nodes, then one calls k-uniform .


  • Always applies . Equality occurs z. B. for complete graphs , generally for regular graphs .
  • The following applies , where denotes the number of edges of the graph. Since the sum of the node degrees is always even, the number of nodes with an odd degree is always even.

Planar graphs

Related planar graphs with nodes , edges , and satisfy the inequality , because each surface adjacent to at least three edges and each edge bounded exactly two surfaces. From this and from the equation ( Euler's polyhedron equation ) it follows and it follows for the average degree of the node

This means that for finite planar graphs the average nodal degree is less than 6. Graphs with a higher average nodal degree cannot be planar.


The degree is one of the basic concepts of graph theory and provides many important estimates for graph properties such as B. the edge coloring number .