juniorGraph Theory

Self-loops and Multiple Edges?

Updated Apr 28, 2026

Short answer

A self-loop is an edge that connects a vertex to itself, while multiple edges are two or more edges connecting the same pair of vertices. These concepts determine whether a graph is considered simple or non-simple and affect how graph algorithms handle connections. Understanding them is important when choosing graph representations and designing traversal or analysis algorithms.

Deep explanation

In graph theory, an edge represents a connection between two vertices. Most basic graph problems assume a simple graph, which has two restrictions:

  • No self-loops.
  • No multiple edges between the same pair of vertices.

When these restrictions are relaxed, we get more general types of graphs.

Self-Loops

A self-loop (also called a loop) is an edge that starts and ends at the same vertex.

Example:

TypeScript
A
   ↺

The edge can be represented as:

TypeScript
(A, A)

In a directed graph, a self-loop means a vertex has an edge pointing back to itself.

Example:

TypeScript
A → A

In an undirected graph, the self-loop contributes twice to the degree of the vertex because the edge touches the vertex at both ends.

Example:

TypeScript
Degree(A) = 2

Self-loops can represent situations where an object has a relationship with itself, such as:

  • A user following themselves in a social network.
  • A state in an automaton transitioning back to itself.
  • A webpage linking to itself.

Multiple Edges

Multiple edges occur when two vertices have more than one edge connecting them.

Example:

TypeScript
A ─── B
 \   /
  \ /
  B

A cleaner representation:

TypeScript
A ---- B
A ==== B

There are multiple connections between the same pair of vertices.

For a directed graph:

TypeScript
A → B
A → B

The two edges may represent different relationships or events.

Examples:

  • Two cities connected by multiple roads.
  • Two users exchanging different types of messages.
  • Multiple transactions between the same bank accounts.

Graph Types

Graphs are often classified based on whether they allow these features.

Graph TypeSelf-Loops Allowed?Multiple Edges Allowed?
Simple GraphNoNo
MultigraphSometimesYes
PseudographYesYes
Directed GraphDepends on definitionDepends on definition

A simple graph is the most restricted form. A multigraph allows multiple edges but usually does not allow self-loops. A pseudograph allows both.

Impact on Graph Representations

Self-loops and multiple edges influence how graphs are stored.

Adjacency Matrix

For a graph with vertices A, B, and C:

TypeScript
A B C
A   0 2 0
B   2 0 1
C   0 1 0

The value represents the number of edges between vertices.

For multiple edges:

TypeScript
A -- B
A == B

The matrix stores:

TypeScript
matrix[A][B] = 2

For a self-loop:

TypeScript
A → A

The diagonal contains:

TypeScript
matrix[A][A] = 1

Adjacency List

An adjacency list can naturally store multiple edges:

TypeScript
A: [B, B, A]
B: [A, A]

Here:

  • B, B represents two edges between A and B.
  • A represents a self-loop.

Effect on Graph Algorithms

Many graph algorithms assume simple graphs, so self-loops and multiple edges require special handling.

Breadth-First Search (BFS) and Depth-First Search (DFS)

A self-loop does not help discover a new vertex because it points back to the same node.

Example:

TypeScript
A → A

During traversal, the algorithm should recognize that A is already visited.

Multiple edges usually do not change reachability:

TypeScript
A → B
A → B

BFS still discovers B only once.

Degree Calculation

For an undirected graph:

  • A normal edge contributes 1 degree to each endpoint.
  • A self-loop contributes 2 degrees to the same vertex.

Example:

TypeScript
A -- B
A -- A

Degree of A:

TypeScript
1 (from A-B) + 2 (from loop) = 3

When Are They Useful?

Self-loops and multiple edges are not errors; they model real-world relationships that naturally have repeated or internal connections.

They are useful in:

  • Network modeling.
  • State machines.
  • Transportation systems.
  • Database relationship graphs.
  • Multigraph representations of complex relationships.

Real-world example

Consider a flight network:

  • Vertices represent airports.
  • Edges represent flights.

A normal graph might contain:

TypeScript
New York → London

A multiple-edge graph can represent several flights:

TypeScript
New York → London (Morning flight)
New York → London (Evening flight)

These are different edges because they represent different available connections.

A self-loop could represent a training flight:

TypeScript
Pilot Training Center → Pilot Training Center

where an aircraft leaves and returns to the same airport.

A simple representation:

Python
flights = {
    "NY": ["LON", "LON"],
    "TRAINING": ["TRAINING"]
}


print(flights["NY"])

Output:

TypeScript
["LON", "LON"]

The repeated "LON" entries represent multiple edges, while "TRAINING" pointing to itself represents a self-loop.

Common mistakes

  • * Assuming every graph is a simple graph and ignoring the possibility of loops or repeated edges.
  • * Counting a self-loop as contributing only one degree in an undirected graph.
  • * Removing duplicate edges when the duplicates represent meaningful separate relationships.
  • * Treating multiple edges as creating new vertices instead of additional connections.
  • * Forgetting that some algorithms need modifications when graphs contain self-loops or parallel edges.
  • * Confusing multiple edges with an edge connecting more than two vertices, which is a hyperedge.

Follow-up questions

  • What is the difference between a simple graph and a multigraph?
  • How does a self-loop affect the degree of a vertex in an undirected graph?
  • Can BFS or DFS handle graphs with multiple edges?
  • Why would a real-world system use multiple edges instead of one edge with extra data?
  • How are self-loops represented in an adjacency matrix?
  • Are self-loops allowed in directed graphs?

More Graph Theory interview questions

View all →