Graph loop
A loop is where a vertex on a graph has an edge that connects back to itself. In other words, the edge starts and ends at the same vertex.
A loop is an edge that connects a vertex to itself.
Loops and vertex degrees
- If a vertex has a loop, its degree increases by 2, since the loop technically attaches to the vertex twice (once at each end).
- This only applies if the graph is not directed.
Simple graphs
- A simple graph is a graph that does not allow loops or multiple edges between the same pair of vertices.
- This means that loops can’t exist in simple graphs.
flashcards
| Question | Answer |
|---|---|
| What is a loop in a graph? | An edge that connects a vertex to itself. |
| By how much does a loop increase the degree of a vertex in an undirected graph? | The degree increases by 2. |
| Does the rule for loop degree increase (by 2) apply to directed graphs? | No, it only applies if the graph is not directed. |
| What is a simple graph? | A graph that does not allow loops or multiple edges between the same pair of vertices. |
| Can loops exist in a simple graph? | No, loops cannot exist in simple graphs. |