In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a loop (also called a self-loop or a "buckle") is an edge that connects a vertex

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 to itself. A simple graph contains no loops.

Depending on the context, a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 or a multigraph

Multigraph

In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....

 may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges

Multiple edges

In graph theory, multiple edges , are two or more edges that are incident to the same two vertices...

 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".

Degree

For an undirected graph, the degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum 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

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

, a loop adds one to the in degree and one to the out degree

See also

• Cycle (graph theory)
  Cycle (graph theory)
  In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
  
  
• List of cycles

Loops in Topology

• Möbius ladder
  Möbius ladder
  In graph theory, the Möbius ladder Mn is a cubic circulant graph with an even number n of vertices, formed from an n-cycle by adding edges connecting opposite pairs of vertices in the cycle...
  
  
• Möbius strip
  Möbius strip
  The Möbius strip or Möbius band is a surface with only one side and only one boundary component. The Möbius strip has the mathematical property of being non-orientable. It can be realized as a ruled surface...
  
  
• Strange loop
  Strange loop
  A strange loop arises when, by moving up or down through a hierarchical system, one finds oneself back where one started.Strange loops may involve self-reference and paradox...
  
  
• Klein bottle
  Klein bottle
  In mathematics, the Klein bottle is a non-orientable surface, informally, a surface in which notions of left and right cannot be consistently defined. Other related non-orientable objects include the Möbius strip and the real projective plane. Whereas a Möbius strip is a surface with boundary, a...