Loop (graph theory)
Edge that connects a node to itself
In graph theory, a loop (also called a self-loop or a buckle) is an edge that connects a vertex to itself. A simple graph contains no loops.
Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges between the same vertices):
- Where graphs are defined so as to allow loops and multiple edges, a graph without loops or multiple edges is often distinguished from other graphs by calling it a simple graph.
- Where graphs are defined so as to disallow loops and multiple edges, a graph that does have loops or multiple edges is often distinguished from the graphs that satisfy these constraints by calling it a multigraph or pseudograph.
In a graph with one vertex, all edges must be loops. Such a graph is called a bouquet.
01Degree
For an undirected graph, the degree of a vertex is equal to the number of adjacent vertices.
A special case is a loop, which adds two to the degree. This can be understood by letting each connection of the loop edge count as its own adjacent vertex. In other words, a vertex with a loop "sees" itself as an adjacent vertex from both ends of the edge thus adding two, not one, to the degree.
For a directed graph, a loop adds one to the in degree and one to the out degree.
Sources and credits
This article is adapted from the Wikipedia article “Loop (graph theory)”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Images, from Wikimedia Commons:
- 6n-graph2.svg by Unknown author, Public domain
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.
