The degree of a vertex in an undirected graph

In graph theory, a graph consists of vertices and edges connecting these vertices (though technically it is possible to have no edges at all.) The degree of a vertex represents the number of edges incident to that vertex. In this lesson, we will explore what that means with examples and look at different cases where the degree might not be as simple as you would guess.

Table of Contents

  1. The degree of a vertex in a simple graph
  2. Multigraphs and the degree of a vertex
  3. Pseudographs and the degree of a vertex
  4. Summary
advertisement

The degree of a vertex in a simple graph

A simple graph is the type of graph you will most commonly work with in your study of graph theory. In these types of graphs, any edge connects two different vertices. An example of a simple graph is shown below.

An example of a simple graph. There are 5 vertices. Each edge connects two different vertices.

We can label each of these vertices, making it easier to talk about their degree. When you are trying to determine the degree of a vertex, count the number of edges connecting the vertex to other vertices.

A graph with five vertices. They have been labelled v1, v2, v3, v4, and v5.

Consider first the vertex \(v_1\). There are two edges incident with this vertex. Therefore, \(v_1\) has degree 2.

The vertex labelled v1 has 2 edges connected to it. Therefore the degree of the vertex is 2.

Using a common notation, we can write: \(\text{deg}(v_1) = 2\).

In fact, the degree of \(v_4\) is also 2. Vertex \(v_2\) has 3 edges connected to it, so its degree is 3. Vertex \(v_3\) has only one edge connected to it, so its degree is 1, and \(v_5\) has no edges connected to it, so its degree is 0.

Graph with the degree of each vertex shown. There is one vertex of degree 3, two vertices of degree 2, one of degree 1, and one of degree 0.

Not all graphs are simple graphs. We still must consider two other cases: multigraphs and pseudographs.

Multigraphs and the degree of a vertex

Multigraphs allow for multiple edges between vertices. An example of a multigraph is shown below.

An example of a multigraph. There are four vertices. The vertex v1 and vertex v2 are connected by three edges. This is why this is a multigraph and not a simple graph.

In a multigraph, the degree of a vertex is calculated in the same way as it was with a simple graph. In the graph above, the vertex \(v_1\) has degree 3, since there are 3 edges connecting it to other vertices (even though all three are connecting it to \(v_2\)).

Graph showing the degree of a vertex in a multigraph. The vertex v1 has three edges incident to it (connecting it to other vertices), so it has degree 3 even though all three edges connect it to v2.

We can now use the same method to find the degree of each of the remaining vertices.

Image showing the degree of each vertex in a multigraph. The vertex v1 has 3 edges connected to it, so its degree is 3. v2 has 5 edges incident to it, so its degree is 5. v3 and v4 each have only one edge incident to them, so their degrees are each 1.

Hint: You can check your work by using the handshaking theorem. It states that the sum of all the degrees in an undirected graph will be 2 times the number of edges. In the example above, the sum of the degrees is 10 and there are 5 total edges.

Pseudographs and the degree of a vertex

Pseudographs are not covered in every textbook, but do come up in some applications. These are graphs that allow a vertex to be connected to itself with a loop. In the example below, we see a pseudograph with three vertices. Vertex v2 and vertex v3 each have an edge connecting the vertex to itself.

A pseudograph with three vertices. Two of the vertices are connected to themselves with an edge, called a loop.

When calculating the degree of a vertex in a pseudograph, the loop counts twice.

A pseudograph showing the degree of each vertex. Vertex v1 has one edge connected to it, so its degree is 1. Vertex v2 has two edges connected to it and a loop, so its degree is 4. Vertex v3 has one edge and a loop, so its degree is 3.

In the graph above, vertex \(v_2\) has two edges incident to it. But, it also has a loop (an edge connecting it to itself). This adds 2 to the degree, giving this vertex a degree of 4. Similarly, \(v_3\) has one edge incident with it, but also has a loop. Therefore its degree is 3.

Note that with this convention, the handshaking theorem still applies to the graph. There are 4 edges, since each loop counts as an edge and the total degree is:

\(1 + 4 + 3 = 8 = 2 \times \text{(number of edges)}\)

advertisement

Summary

The degree of a vertex is the number of edges incident to the vertex. This is simply a way of saying “the number of edges connected to the vertex”. It is common to write the degree of a vertex v as deg(v) or degree(v). If you are working with a pseudograph, remember that each loop contributes 2 to the degree of the vertex.

Subscribe to our Newsletter!

We are always posting new free lessons and adding more study guides, calculator guides, and problem packs.

Sign up to get occasional emails (once every couple or three weeks) letting you know what's new!

Copyright 2010- 2017 MathBootCamps | Privacy Policy