Degree (graph theory)

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.

definition

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. ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle d_{G}(v)}$ ${\displaystyle G}$ ${\displaystyle v}$

Instead is often the notation used. The index can be omitted if it is clear which graph it is. ${\displaystyle d_{G}(v)}$ ${\displaystyle \deg _{G}(v)}$ ${\displaystyle G}$

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. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \delta (G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \Delta (G)}$ ${\displaystyle G}$ ${\displaystyle d(G)}$

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 . ${\displaystyle G}$ ${\displaystyle d_{G}^{-}(v)}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle d_{G}^{+}(v)}$

Here is the number of all edges that end in and the number of all edges that start in. ${\displaystyle d_{G}^{-}(v)}$ ${\displaystyle v}$ ${\displaystyle d_{G}^{+}(v)}$ ${\displaystyle v}$

A node without input edges ( ) is called a source , a node without output edges ( ) is called a sink . ${\displaystyle d_{G}^{-}(v)=0}$ ${\displaystyle d_{G}^{+}(v)=0}$

Related terms

• A node is said to be isolated if it:
  • in an undirected graph : has no neighbors . ${\displaystyle d_{G}=0}$
  • in a directed graph : has no predecessors and no successors. . ${\displaystyle d_{G}^{+}=d_{G}^{-}=0}$

• 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 . ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$

• 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 . ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$

• 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 . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$

properties

• Always applies . Equality occurs z. B. for complete graphs , generally for regular graphs . ${\displaystyle \delta (G)\leq d(G)\leq \Delta (G)}$
• 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. ${\displaystyle 2\cdot |E|=\sum _{v\in V(G)}d_{G}(v)}$ ${\displaystyle |E|}$

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 ${\displaystyle |V|}$ ${\displaystyle |E|}$ ${\displaystyle |F|}$ ${\displaystyle 2\cdot |E|\geq 3\cdot |F|}$ ${\displaystyle |V|-|E|+|F|=2}$ ${\displaystyle |E|\leq 3\cdot |V|-6}$

${\displaystyle d(G)={\frac {\sum _{v\in V}d_{G}(v)}{|V|}}={\frac {2\cdot |E|}{|V|}}\leq {\frac {2\cdot (3\cdot |V|-6)}{|V|}}={\frac {6\cdot |V|-12}{|V|}}<6}$

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.

use

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 .

literature

• Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 .