Fact-checked by Grok 2 weeks ago

Simple path

In graph theory, a simple path is a path—a sequence of edges connecting a sequence of vertices—such that no vertex appears more than once.^[1] This distinguishes it from a trail, which allows repeated vertices but not edges, and ensures the path is "self-avoiding" in terms of nodes.^[2] Simple paths form the basis for analyzing graph connectivity, where a graph is connected if there exists a simple path between every pair of vertices.^[3] They are crucial in algorithms for finding shortest paths, such as Dijkstra's algorithm, and in problems like determining Hamiltonian paths, which visit each vertex exactly once.^[4] In directed graphs, simple paths respect edge directions while maintaining the no-repeat-vertex property.^[5]

Definition

Formal definition

In graph theory, a simple path in an undirected graph G = (V, E) is defined as a sequence of distinct vertices v_0, v_1, \dots, v_k where k \geq 0, such that for each i = 0, 1, \dots, k-1, the edge \{v_i, v_{i+1}\} belongs to E.^[6]^[7] This definition assumes familiarity with basic concepts such as vertices V, edges E, and undirected graphs where edges connect pairs of vertices without direction.^[6] The case k = 0 corresponds to the trivial simple path consisting of a single vertex with no edges, often referred to as a path of length 0.^[7]^[8] For directed graphs (digraphs) D = (V, A), where A denotes the set of directed arcs, a simple path is a sequence of distinct vertices v_0, v_1, \dots, v_k with k \geq 0, such that for each i = 0, 1, \dots, k-1, the directed arc (v_i, v_{i+1}) belongs to A.^[6]^[7] The trivial case of a single vertex applies similarly, assuming standard terminology for vertices, arcs, and directed graphs where arcs have orientation from tail to head.^[6]

Notation and terminology

In graph theory, a simple path is commonly denoted by a sequence of its vertices, such as P = (v_0, v_1, \dots, v_k), where v_0, v_1, \dots, v_k are distinct vertices and each consecutive pair (v_i, v_{i+1}) is connected by an edge for i = 0, 1, \dots, k-1.^[9] This notation explicitly lists the vertices traversed, emphasizing the absence of repetitions. Alternatively, a simple path connecting specific endpoints may be abbreviated as P_{v_0 v_k}, highlighting the starting vertex v_0 and ending vertex v_k without enumerating all intermediate vertices.^[10] Standard terminology includes the "simple path from u to v", which specifies a simple path beginning at vertex u and terminating at vertex v. The term "vertex-simple path" is used to underscore that no vertex appears more than once along the path, distinguishing it from paths that might repeat vertices but not edges.^[11] Additionally, an "open simple path" refers to a simple path whose endpoints are distinct, in contrast to closed structures like cycles where the start and end coincide.^[12] The length of a simple path P = (v_0, v_1, \dots, v_k) is defined as the number of edges it contains, denoted |P| = k, rather than the number of vertices.^[13] In this convention, the initial vertex v_0 serves as the starting point, the terminal vertex v_k as the endpoint, and the vertices v_1, \dots, v_{k-1} as the internal vertices.^[9] The concept of a "simple path" was formalized in foundational graph theory literature during the mid-20th century, building on earlier discussions of paths in works such as Dénes König's 1936 treatise on finite and infinite graphs.^[14]

Properties

Structural properties

A simple path in a graph is inherently acyclic, as any cycle would necessitate the repetition of a vertex, which is forbidden by definition.^[15] This acyclicity ensures that simple paths form tree-like structures without loops, distinguishing them from more permissive traversals.^[16] A key structural feature is the subpath property: any contiguous sequence of vertices within a simple path itself forms a simple path, preserving the no-repeat-vertex rule.^[15] This property allows simple paths to be decomposed into smaller simple paths without altering their fundamental characteristics.^[16] The subgraph defined by the vertices and edges of a simple path is a path graph, a connected tree in which every vertex has degree at most 2, with exactly two vertices of degree 1 (the endpoints) unless the path is trivial.^[15] This subgraph is induced only if no additional edges exist between its vertices in the original graph; otherwise, chords may create a denser structure.^[16] In disconnected graphs, simple paths exist solely within a single connected component, as the absence of edges between components prevents paths from spanning multiple parts.^[15] Thus, the connected components partition the possible simple paths of the graph.^[16] The no-revisit-vertex rule of simple paths inherently limits their extent compared to general walks, which can return to vertices arbitrarily, allowing for longer or more exploratory traversals in the same graph.^[15]

Length and uniqueness

The length of a simple path P in a graph is defined as the number of edges in P, often denoted as |P| or \ell(P).^[17]^[18] For a simple path connecting k+1 distinct vertices, this length is exactly k.^[19] No simple path in a graph G = (V, E) with n = |V| vertices can have length greater than n-1, as a longer path would require at least n+1 vertices by the pigeonhole principle, forcing repetition of a vertex and violating the simple path condition.^[20] This upper bound is tight, achieved in path graphs where the longest simple path spans all vertices. The maximum length of any simple path in G is thus at most n-1, though it relates to the graph's diameter—the maximum shortest-path distance between any pair of vertices—which cannot exceed this cap.^[5] In trees, which are connected acyclic graphs, there is exactly one simple path between any two distinct vertices u and v.^[19]^[21] This uniqueness follows from the absence of cycles, ensuring no alternative routes exist without repeating vertices. In contrast, general graphs may contain multiple simple paths between u and v, potentially of varying lengths.^[22] The graph distance d(u, v) between vertices u and v is the length of the shortest simple path connecting them, formally defined as

d(u, v) = \min \{ |P| : P \text{ is a simple path from } u \text{ to } v \}.

If no such path exists, d(u, v) = \infty.^[5]^[2] This metric quantifies the minimal number of edges needed to reach v from u without vertex repetition.

Distinction from walks and trails

In graph theory, a walk is defined as an alternating sequence of vertices and edges, starting and ending at vertices, where vertices and edges may be repeated, allowing for general traversals that can include backtracking or revisiting parts of the graph.^[16] A trail is a special type of walk in which no edge is repeated, though vertices may be repeated; this structure is exemplified by Eulerian paths, which traverse every edge exactly once but may return to the same vertex multiple times.^[16] A simple path, by contrast, is a trail with the additional restriction that no vertex is repeated (except possibly the starting and ending vertices in the case of a closed variant, though the focus here is on open paths), which automatically ensures no edges are repeated either. This makes the simple path stricter than both walks and trails: every simple path is a trail and a walk, but the converse does not hold, as trails and walks permit vertex repetitions that simple paths forbid. To illustrate, consider a graph consisting of two cycles sharing a single vertex (e.g., a figure-8 graph). An Eulerian circuit that traverses the first cycle and then the second, starting and ending at the shared vertex, constitutes a closed trail (since each edge is used exactly once) but is not a simple path because it repeats the shared vertex internally, violating the no-repetition rule for vertices beyond the endpoints. In undirected graphs, trails can thus exceed the length of simple paths, as they allow vertex revisits without reusing edges, enabling longer routes in graphs with high vertex degrees or multiple edges incident to the same vertices.^[16]

Simple cycles and circuits

A simple cycle in a graph is a closed simple path in which the starting and ending vertices are the same, but no other vertices are repeated. Formally, it is a sequence of distinct vertices v_0, v_1, \dots, v_k (with k \geq 3) connected by edges such that v_k is adjacent to v_0, and all v_i for $0 \leq i \leq k are distinct except for the identification of the endpoints.^[23]^[24] In contrast, a circuit is a closed trail, meaning a walk that starts and ends at the same vertex with no repeated edges, though vertices other than the endpoints may repeat.^[25] A simple cycle is thus a special case of a circuit where no vertices are repeated (except the endpoints), ensuring both no repeated vertices and no repeated edges.^[23] The girth of a graph is defined as the length of its shortest simple cycle, providing a measure of the graph's cyclomatic structure.^[23] In undirected simple graphs, every simple cycle has length at least 3, as shorter cycles would require loops or multiple edges, which are absent in such graphs.^[23] Additionally, a chordless simple cycle, which contains no edges connecting non-consecutive vertices in the cycle, is known as an induced cycle, forming an induced subgraph isomorphic to a cycle graph.^[26] The length of a simple cycle C, denoted |C|, equals the number k of its edges (and also its vertices, excluding the repetition of the starting vertex).^[23]

Algorithms

Detection and existence

In connected undirected graphs, a simple path exists between any pair of distinct vertices, as the connectivity ensures a route without repeated vertices can be found by traversing the graph structure. This existence can be verified efficiently using breadth-first search (BFS) or depth-first search (DFS), both of which explore the graph from a source vertex until reaching the target, marking visited vertices to avoid cycles and confirming reachability in linear time, specifically O(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges.^[27] For finding the shortest simple path in graphs with non-negative edge weights, Dijkstra's algorithm is the standard method, prioritizing vertices by tentative distances using a priority queue to ensure the first path to a vertex is the shortest and inherently simple, as it never revisits nodes. With a binary heap implementation, it achieves a time complexity of O((|V| + |E|) \log |V|), making it suitable for sparse graphs where efficiency is critical.^[28]^[27] In directed graphs, the existence of a simple path from one vertex to another equates to reachability, since any path can be shortened to a simple one by eliminating cycles; this is checked using DFS with backtracking, maintaining a set of vertices in the current path to prevent revisits and exploring outgoing edges recursively until the target is found or all branches are exhausted, again in O(|V| + |E|) time. The existence of a simple path is also equivalent to an entry in the graph's transitive closure, which captures all pairwise reachabilities, though direct search methods like DFS are preferred over computing the full closure due to lower overhead for single queries.^[27] When edge weights may be negative but no negative cycles are present, the Bellman-Ford algorithm computes the shortest simple path by iteratively relaxing all edges up to |V|-1 times, followed by a check for negative cycles via an additional relaxation pass; if no further updates occur, the computed paths are simple and optimal, with a time complexity of O(|V| |E|). This approach handles negative weights where Dijkstra's cannot, provided the absence of reachable negative cycles is verified to ensure finite shortest paths.^[27]

Enumeration and counting

Enumerating all simple paths between two vertices u and v in a graph typically employs backtracking algorithms, such as depth-first search (DFS) modified with a visited set to ensure no vertex is repeated.^[29] This approach systematically explores potential paths, pruning branches that would revisit vertices, and is exhaustive but computationally intensive due to the exponential growth in the number of possible paths. The time complexity of such backtracking is generally O(\Delta^d), where \Delta is the maximum degree of the graph and d is the distance between u and v, reflecting the branching factor at each step.^[30] Counting the number of simple paths between two vertices is a #P-complete problem, even in directed graphs, making exact computation intractable for large graphs.^[31] In directed acyclic graphs (DAGs), however, dynamic programming can efficiently count all paths from u to v in polynomial time, as the absence of cycles ensures all paths are simple; the standard recurrence computes the number of paths to v by summing over incoming edges after topological sorting.^[32] For general graphs, inclusion-exclusion principles have been adapted in variants to derive exact counts by subtracting overcounts of non-simple paths, though these remain exponential in practice.^[33] In trees, the count of simple paths between any two vertices is exactly 1, as trees are connected acyclic graphs with a unique path connecting every pair of distinct vertices.^[34] In grid or lattice graphs, counting simple paths—equivalently, self-avoiding walks—relies on recursive formulas derived from lace expansions or generating functions, which provide asymptotic growth rates like the connective constant \mu, but exact enumeration lacks closed forms and uses series expansions for small lengths.^[35] Related to enumeration, finding the longest simple path in a graph is NP-hard, underscoring the inherent difficulty of path-related optimization.^[36] Overall, enumeration and counting of simple paths are #P-hard, even for the counting variant alone. Modern approaches enhance backtracking with pruning techniques, such as restricting to vertices in the scope between source and target, to reduce the effective search space in real-world networks.^[29] Variants of the matrix-tree theorem enable counting in specific cases like arborescences or trees, but do not extend to general simple paths due to the #P-completeness barrier.^[30]

Applications

In graph connectivity

In graph theory, connectivity is fundamentally characterized by the existence of simple paths. An undirected graph is defined as connected if there exists at least one simple path between every pair of distinct vertices.^[37] This property ensures that the graph forms a single component without isolated parts. For higher degrees of connectivity, a graph is k-vertex-connected if it remains connected after the removal of any set of fewer than k vertices. Menger's theorem provides a precise duality here: the size of the minimum vertex cut separating two non-adjacent vertices u and v equals the maximum number of internally vertex-disjoint simple paths connecting u and v.^[38] Simple paths also underpin key metrics of graph structure. The diameter of a connected graph is the maximum length of the shortest simple path over all pairs of vertices, quantifying the graph's overall "spread."^[39] Complementing this, the eccentricity of a vertex v is the length of the longest shortest simple path from v to any other vertex, with the graph's radius being the minimum eccentricity and the diameter the maximum.^[40] These measures, derived solely from simple paths, reveal central versus peripheral vertices and the graph's compactness. Critical elements like bridges and articulation points highlight vulnerabilities in connectivity via simple paths. A bridge is an edge whose removal disconnects the graph by eliminating all simple paths between the components it links.^[41] Similarly, an articulation point (or cut vertex) is a vertex whose removal increases the number of connected components, as it lies on all simple paths connecting certain pairs across those components.^[42] In directed graphs, strong connectivity requires a simple path from every vertex to every other, implying bidirectional simple paths between any pair in strongly connected components.^[43] Simple paths further define the block structure of graphs, decomposing them into blocks—maximal subgraphs without articulation points, also known as biconnected components. Within each block, any two vertices are joined by at least two internally vertex-disjoint simple paths, ensuring local robustness; the overall structure emerges from how these blocks share articulation points or bridges.^[44] This decomposition uses simple paths to delineate regions of high internal connectivity while exposing the graph's hierarchical fault lines.

In optimization problems

Simple paths are integral to numerous optimization problems in graph theory and computer science, where the constraint of visiting vertices at most once introduces computational challenges that model real-world constraints like resource non-reuse or cycle avoidance. A key example is the Hamiltonian path problem, which requires identifying a simple path that visits every vertex in a graph exactly once. Determining whether such a path exists is NP-complete, as proven by Karp through reductions from satisfiability in his seminal 1972 paper.^[45] Similarly, the traveling salesman problem (TSP) seeks the shortest Hamiltonian cycle—a simple cycle traversing all vertices exactly once—often formulated with edge weights representing distances between cities. The decision version of TSP is also NP-complete (Karp, 1972), and while exact solutions remain intractable for large instances, approximation algorithms like Christofides' 1.5-approximation leverage simple paths in subgraphs, such as minimum spanning trees, to construct near-optimal tours.^[45] Another fundamental optimization involves maximizing the length of a simple path, known as the longest simple path problem, which is NP-hard even in unweighted graphs due to its reduction from the Hamiltonian path problem (Garey and Johnson, 1979). This arises in scheduling applications, where tasks must be sequenced without revisiting processors, or in routing scenarios prohibiting vertex returns to optimize coverage without redundancy. In network flow contexts, simple paths enable maximum capacity optimization; the Ford-Fulkerson algorithm iteratively augments flow along simple paths from source to sink in the residual graph, ensuring no vertex repetitions to avoid cycles and guarantee termination with integer capacities (Ford and Fulkerson, 1956). For vertex-disjoint simple paths, Menger's theorem equates their maximum number to the size of the minimum vertex cut separating non-adjacent vertices, providing an exact optimization bound. In contemporary applications, simple paths address optimization without repeats in specialized domains. In bioinformatics, genome assembly pipelines use simple paths in overlap-layout-consensus graphs to reconstruct contigs from sequencing reads, avoiding repeats that could introduce assembly errors or chimeras (Kececioglu and Myers, 2008). Likewise, in AI planning, simple paths in state transition graphs model action sequences that reach goals without state revisits, ensuring acyclic plans and computational efficiency in algorithms like A* search (LaValle, 2006).

References

[1]
[PDF] graph theory: basic definitions and theorems
A trail is a walk with no repeated edges. A path is a walk with no repeated vertices. A circuit is a closed trail and a trivial circuit has a single vertex and ...
[2]
[PDF] Graph Theory Fundamentals
A path is called simple or self-avoiding if it does not repeat any nodes. Example of a simple path between a and h. Page 23. How Many Paths Are There?
[3]
[PDF] Math 776 Graph Theory Lecture Note 1 Basic concepts
A u, v-walk is a walk with v0 = u and vk = v. A trail is a walk with no repeated edge. A path is a walk with no repeated vertices. A closed walk is ...<|control11|><|separator|>
[4]
[PDF] graph definitions - Basic Combinatorics
So a walk is any kind of continuous perambulation; a trail doesn't visit the same edge twice (but may visit a vertex multiple times) and a path neither visits ...
[5]
Notation for Graphs
Basic Graph Notations and Definitions ; simple path, A path with no repeated nodes. ; Cycle, A path u1,…,uk is a cycle if (1) u1=uk, (2) u1,…,uk−1 are distinct, ( ...
[6]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book introduces graph theory, presenting basic material and applications to math and real-world problems, with new proofs and efficient methods.
[7]
[PDF] Diestel: Graph Theory - PRIP
Page 1. Reinhard Diestel. Graph Theory. Electronic Edition 2000 cс Springer-Verlag New York 1997, 2000. This is an electronic version of the second (2000) ...
[8]
[PDF] Chapter 2 Graphs - CS@Cornell
This idea motivates the definition of a path in a graph: a path is simply a sequence of nodes with the property that each consecutive pair in the sequence is ...
[9]
[PDF] Simple Path Covers in Graphs
Definition 2.1 A simple path cover of a graph G is a path cover ψ of G such that any two paths in ψ have at most one vertex in common. The minimum cardinality ...
[10]
[PDF] Graph Theory - HKUST Math Department
Since P(v0,u) and Q(v0,v) are shortest paths, the subpath P(v0,vk) of. P(v0,u) from v0 to vk must be shortest; so is the subpath Q(v0,vk) of Q(v0,v) from v0 to ...
[11]
[PDF] The weighted matching approach to maximum cardinality matching
A vertex is free if it is not on any matched edge. An alternating path is a vertex-simple path whose edges are alternately matched and unmatched. (Paths of 0 or ...
[12]
[PDF] Chapter 3 Graphs, Part I: Basic Notions - Penn Engineering
Given a directed graph, G, intuitively, a path from a node u to a node v is a way to travel from u in v by following edges of the graph that “link up correctly” ...
[13]
Graph Path -- from Wolfram MathWorld
The length of a path is the number of edges it contains. In most contexts, a path must contain at least one edge, though in some applications (e.g., defining ...
[14]
Theory of Finite and Infinite Graphs
Konig, D. (Denes), 1884-1944. [Theorie der endlichen und unendlichen Graphen. English]. Theory of finite and infinite graphs 1 Denes Konig ; translated by.
[15]
[PDF] The Basics
In general, every walk between two vertices contains4 a path between these vertices. (proof?). 1.4 Connectivity. A graph G is called connected if it is non- ...
[16]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book introduces graph theory, presenting basic material and applications to math and real-world problems, with new proofs and efficient methods.Missing: v_k} | Show results with:v_k}
[17]
4.4 Introduction to Graph Theory
A graph has vertices and edges. Adjacent vertices are connected by an edge. A path is a graph with edges between consecutive vertices. A cycle is a path with ...
[18]
[PDF] Chapter 2 Mathematical Preliminaries
In an undirected graph a (simple) cycle is a path that starts and ends at the same vertex, has no repeated vertices other than the first and last, and has ...
[19]
[PDF] Lecture #22: Graphs, Paths, and Trees
Mar 14, 2012 · A graph has nodes and edges. A path is a sequence of edges. A tree is a connected, undirected graph with no cycles.
[20]
[PDF] 4 Shortest Paths in Graphs
We could ask for a shortest simple path. However, this problem is NP-hard in ... at most n - 1 edges. Now the algorithm is guaranteed to be correct ...
[21]
[PDF] CS311H: Discrete Mathematics Graph Theory III Trees Fact About ...
Theorem: An undirected graph G is a tree if and only if there is a unique simple path between any two of its vertices.
[22]
[PDF] Chapter 11 - Computer Science
Theorem: An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. Proof: Assume that T is a tree.
[23]
Graph Cycle -- from Wolfram MathWorld
A graph cycle is a path where the first node corresponds to the last. A graph with at least one cycle is called a cyclic graph.
[24]
graph theory - What is the right definition of a cycle?
May 3, 2017 · A cycle is a non-trivial path whose first and last vertices are the same, but no other vertex is repeated.
[25]
Graph Theory | SpringerLink
Jul 27, 2019 · Definition 12.16. A circuit or cycle in a graph is a closed trail. A circuit is also called elementary cycle, circular path, and polygon.
[26]
Chordless Cycle -- from Wolfram MathWorld
A chordless cycle in G is a cycle of length at least 4 in G that has no chord (that is, the cycle is an induced subgraph).
[27]
Introduction to Algorithms - MIT Press
Introduction to Algorithms. fourth edition. by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Hardcover ...Missing: BFS DFS path
[28]
A note on two problems in connexion with graphs
On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem. Proc. Amer. Math. Soc.7, 48–50 (1956).
[29]
[PDF] Effectively Counting s − t Simple Paths in Directed Graphs - arXiv
Jun 30, 2022 · In an exact algorithm for counting s − t simple paths that exhaustively enumerates all simple paths from s to t, we can use backtracking: we ...
[30]
None
### Summary of Time Complexity for Enumeration of Simple Paths Using Backtracking or Other Methods
[31]
[PDF] Lecture Note 2 2.1 #P-Completeness 2.2 The permanent
Let #(s, t)-PATHS be the problem of counting the number of simple paths between vertices s and t in a graph G. Theorem 2.4. #(s, t)-PATHS is #P-complete. Proof.
[32]
Number of paths from source to destination in a directed acyclic graph
Jul 11, 2025 · The idea is to perform a Depth First Search traversal starting from the source node and count the number of paths reaching destination node.
[33]
Enumerating Simple Paths from Connected Induced Subgraphs
Oct 25, 2018 · In the literature, variants of the inclusion–exclusion principle led to discovering exact formulas for counting simple paths and cycles on ...<|control11|><|separator|>
[34]
Trees - Discrete Mathematics
This works because there is a unique path between any two vertices in a tree. So from any vertex, we can travel back to the root in exactly one way. This also ...
[35]
[PDF] Lectures on Self-Avoiding Walks - IHES
Abstract. These lecture notes provide a rapid introduction to a number of rigorous results on self-avoiding walks, with emphasis on the critical behaviour.
[36]
[PDF] Solving the Longest Simple Path Problem with Heuristic Search
LSP is a fundamental problem in graph theory, that is known to be NP-hard, and even hard to approximate within a con- stant factor (Karger, Motwani, and ...
[37]
Connected Graph -- from Wolfram MathWorld
A connected graph is graph that is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph.
[38]
Menger's Theorem -- from Wolfram MathWorld
Menger's Theorem. See. Menger's n-Arc Theorem · About MathWorld · MathWorld Classroom · Contribute · MathWorld Book · wolfram.com · 13,278 Entries · Last ...<|control11|><|separator|>
[39]
Graph Diameter -- from Wolfram MathWorld
The graph diameter of a graph is the length max_(u,v)d(u,v) of the longest shortest path (ie, the longest graph geodesic) between any two graph vertices.Missing: simple | Show results with:simple
[40]
Graph Eccentricity -- from Wolfram MathWorld
The eccentricity epsilon(v) of a graph vertex v in a connected graph G is the maximum graph distance between v and any other vertex u of G.
[41]
Graph Bridge -- from Wolfram MathWorld
A bridge is an edge of a not-necessarily-connected graph G whose removal increases the number of components of G.
[42]
Articulation Vertex -- from Wolfram MathWorld
An articulation vertex of a not-necessarily-connected graph is a vertex whose removal increases the connected component count.
[43]
Strongly Connected Component -- from Wolfram MathWorld
A strongly connected component of a simple directed graph (i.e., a digraph without loops) is a maximal subdigraph such that for every pair of distinct ...
[44]
Block -- from Wolfram MathWorld
If a block has more than two vertices, then it is biconnected. The blocks of a loopless graph are its isolated points, bridges, and maximal 2-connected ...
[45]
[PDF] reducibility among combinatorial problems - CS@Purdue
The main object of this paper is to establish that a large number of important computational problems can play the role of. SATISFIABILITY in Cook's theorem.