Loop (Graph Theory)¶
A graph edge whose two endpoints are the same vertex, admitted or excluded according to the chosen graph category.
Core Idea¶
A graph-theoretic loop is a local edge relation, not merely any return to a starting point. Both ends of one edge coincide at one vertex; in directed language its source and target are identical.
Whether loops exist is part of the graph's type. Their double incidence in undirected graphs and their diagonal representation in adjacency matrices must be handled explicitly when computing invariants.
Structural Signature¶
Sig role-phrases:
- Graph — Supplies vertices, edges, and incidence rules. It is ambient structure. Counterfactual: Without a graph category the edge convention is undefined.
- Vertex — Serves as both endpoints of the edge. It is repeated endpoint. Counterfactual: Two distinct endpoints define a non-loop edge.
- Edge — Carries the self-incidence relation. It is defining object. Counterfactual: A walk returning to its start is not itself a loop edge.
- Incidence multiplicity — Counts the edge twice at the same undirected vertex. It is local effect. Counterfactual: Counting it once gives the wrong degree convention.
- Graph-class convention — Determines whether loops and parallel edges are admitted. It is type constraint. Counterfactual: Calling every graph simple silently deletes valid loops.
- Invariant convention — Defines matrix, coloring, and traversal consequences. It is analytic frame. Counterfactual: Results can differ if diagonal entries or loop constraints are treated differently.
What It Is Not¶
- It is not every closed walk or cycle.
- It is not a programming loop.
- It is forbidden in a simple graph by definition.
- A drawn loop still has two undirected incidences at its vertex.
- Closest near-miss. A self-returning closed walk may traverse many edges; a graph-theoretic loop is a single edge incident twice with one vertex.
Scope of Application¶
- Graph theory. Defines pseudographs and local incidence.
- Network modeling. Represents self-relations or within-node transitions.
- Matrix methods. Appears on adjacency diagonals under stated conventions.
- Automata. Represents transitions that retain a state.
Clarity¶
State directedness, graph category, endpoint and incidence conventions, degree counting, adjacency representation, multiplicity, and how loops affect the invariant or algorithm being used.
Manages Complexity¶
The concept compresses a self-relation into one edge while forcing graph models and algorithms to expose assumptions often hidden by simple-graph notation.
Abstract Reasoning¶
- Declare the graph category.
- Inspect each edge's endpoint pair.
- Classify identical endpoints as a loop if permitted.
- Apply incidence and degree conventions.
- Recheck affected matrices, walks, colorings, and algorithms.
Knowledge Transfer¶
Loop-aware results transfer between graph formalisms only after reconciling directedness, multiplicity, degree, and diagonal conventions.
Examples¶
Canonical¶
In a pseudograph with vertex v and edge e having endpoints (v,v), e is a loop; in the undirected degree sum it contributes two at v.
Mapped back: graph → pseudograph; vertex → v; edge → e=(v,v); incidences → 2; degree contribution → 2.
Applied / In Practice¶
Edges v–w and w–v form a length-two closed walk with distinct endpoints on each edge, so neither edge is a loop.
Mapped back: walk → closed; single self-edge → absent; verdict → not loop edge.
Structural Tensions¶
T1 — General Graph Categories versus Simple-Graph Intuition. Loops are legitimate in broad graph models but forbidden by the common simple-graph convention.
Diagnostic: Which graph category is declared?
T2 — Visual Simplicity versus Algebraic Multiplicity. A drawn loop looks like one mark while it has two incidences at its vertex.
Diagnostic: Are degree and matrix conventions stated consistently?
Structural–Framed Character¶
Loop (Graph Theory) is strongly structural as a single edge with coincident endpoints.
Structural Core vs. Domain Accent¶
The skeleton is edge, repeated endpoint, incidence, and graph-type rule. Graph theory supplies degree, adjacency, walks, and coloring consequences.
Instantiates / Related Primes¶
This entry is a kind of Reflexivity (Self-Reference).
-
Approved root. No reviewed parent entails this self-incident edge type.
-
Related — self-loop, pseudograph, cycle, closed walk, and diagonal adjacency entry. They give synonym, host categories, and neighboring structures.
Relationships to Other Abstractions¶
Current abstraction Loop (Graph Theory) Domain-specific
Parents (1) — more general patterns this builds on
-
Loop (Graph Theory) is a kind of Reflexivity (Self-Reference) Prime
A Graph Loop is Reflexivity/Self-Reference realized as an edge whose source and target are the same vertex.The relation returns to its own endpoint, satisfying the reflexive pattern while adding graph-edge semantics. Reflexivity appears in logic, programs, and social relations without graph loops.
Hierarchy path (1) — routes to 1 parentless root
- Loop (Graph Theory) → Reflexivity (Self-Reference)
Neighborhood in Abstraction Space¶
Loop (Graph Theory) sits in a crowded region of the domain-specific corpus (29th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Graph Structures & Algorithms (24 abstractions)
Nearest neighbors
- Utility graph — 0.90
- Prism graph — 0.89
- Graph Power — 0.89
- Prim’s Algorithm — 0.89
- Geodetic Graph — 0.88
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Cycle. Tell: Uses a closed sequence and often multiple edges.
- Closed walk. Tell: May revisit vertices and edges without being one self-edge.
- Parallel edge. Tell: Shares endpoints with another edge but need not be a loop.
- Topological loop. Tell: Is a map or path concept with different structure.
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Loop_(graph_theory) (revision 1285188825).
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.