📂Graph Theory

Graph Theory: Degree

Definition ¹

Let’s assume a directed graph $G$ is given.

If an edge $vw$ exists, we say that the edge leaves from $v$ and enters into $w$.

• The number of edges entering vertex $v$ is called the Indegree and is denoted as $\deg^{-} (v)$.
• The number of edges leaving vertex $v$ is called the Outdegree and is denoted as $\deg^{+}(v)$.
• A vertex that is $\deg^{-} (v) = 0$ is called a Source, and a vertex that is $\deg^{+} (v) = 0$ is called a Sink. A point that is neither a Source nor a Sink is called Internal.

If an edge $vw$ exists, we say that vertex $v,w$ is incident to edge $vw$.

• The number of edges incident to vertex $v$ is called the Degree and is denoted as $\deg (v)$.
• A vertex with a degree of $0$ is called an Isolated Vertex.
• A vertex with a degree of $1$ is called an End Vertex.

The maximum degree of graph $G$ is denoted as $\Delta (G)$, and the minimum degree is denoted as $\delta (G)$.

Explanation

Incidentally, the term “being incident” is not exactly a good euphemism. When two vertices $v,w$ are connected by edge $e$, $v$ and $w$ are said to be Adjacent, and the term “being incident” is used to describe $v,w$ that is attached to edge $e$. Originally, the adjective Incident has meanings such as accompanying or following.

The concept of degree has attracted a lot of interest for a long time in graph theory because it’s an easily conceivable ’number’, especially in pure mathematics where simple graphs are often handled, leading to extensive research on degrees.

Directed Graph

For example, in the following graph, red represents the indegree and blue represents the outdegree. Naturally, the sum of the indegree and outdegree is the same.

Here, a vertex with an indegree of $0$ is called a source. The name source makes sense because it only leaves without entering, similar to sinks and sources in dynamical systems.

Degree

For example, in the next graph, one can calculate the degree of each vertex. Let’s verify that the degree is the sum of the indegree and outdegree when the directed graph is represented as just a simple graph. [ NOTE: A graph with the directions removed like this is called the Underlying Graph of the original directed graph. ]

In the following graph, vertices $C$ and $F$ are End Vertices, and $H$ is an Isolated Vertex.

Note that in applied mathematics, if only $H$ is absent, that is, if the network is fully connected, such a node as $D$ is called a Hub. Hubs typically describe elements that have a significant impact on the entire network or can mediate all communications.

Regular Graph

Especially, a graph where every vertex has the same degree, denoted as $\delta (G) = \Delta (G)$, is called a Regular Graph.