STEP-BY-STEP LESSON · §10.1
Trails, Paths, and Circuits
Distinguish walks, trails, paths, and Euler traversals.
Before you begin
Vertices
Vertices are the graph’s declared objects. An isolated vertex still belongs to the graph even when it has no incident edge. Drawing positions do not change vertex identity.
Edges and graph conventions
Edges connect specified endpoints. State whether edges are directed, whether loops are permitted and whether several different edges may join the same endpoints. A loop contributes two ends to undirected degree.
Symbols
- deg(v)
- degree of vertex v
Definitions and notation for this topic
Loops and parallel edges
A loop has the same endpoint twice. Parallel edges are distinct edges with the same endpoints. For an undirected multigraph, retain each edge’s identity and endpoint pair.
A simple undirected graph excludes both loops and parallel edges. The degree convention does not by itself specify how a matrix should record loops; state the matrix convention explicitly.
Separate glossary example
e₁=AB and e₂=AB are two edges, not one duplicated set entry. A loop e₃=AA contributes two to deg(A).
Degree
deg(v)
In a simple undirected graph, the number of edges incident with a vertex.
In a graph allowing loops, a loop contributes 2 to the degree.
Separate glossary example
In A—B—C, deg(B)=2.
Neighbours and connectedness
N(v)
In a simple undirected graph, N(v) is the set of vertices adjacent to v. The graph is connected when every pair of vertices is joined by a path.
Adjacency means one edge; connectedness permits a longer path. In this simple graph deg(v)=|N(v)|; parallel edges and loops require separate degree conventions.
Separate glossary example
In the path A—B—C, N(B)={A,C}; the graph is connected even though A and C are not adjacent.
Path
A trail with no repeated vertices. A trail is a walk with no repeated edges.
This is the convention in Epp, 5th Metric edition, printed pages 679–680. A walk may repeat vertices and edges.
Separate glossary example
A—B—C
Cycle in a simple undirected graph
In a simple undirected graph, a closed sequence with at least three edges and no repeated vertices other than the start at the end.
Epp calls this a simple circuit. Its first and last vertices coincide; a path cannot repeat that vertex.
The at-least-three-edges restriction belongs to this simple-graph setting. Use the separate walk/trail/circuit entry for the source’s general multigraph convention.
Separate glossary example
A—B—C—A forms a triangle.
Walk, trail and circuit
A walk follows incident vertices and edges; repetition is allowed. A trail has no repeated edge. A circuit is a closed trail with at least one edge. A simple circuit has no repeated vertex except the common first/last vertex.
A path has no repeated vertex. A single vertex is a length-zero walk. Under Epp’s general convention a loop is a one-edge circuit; the at-least-three-edges cycle rule applies only to simple graphs.
Separate glossary example
Traversing one edge A—B and returning along that same edge is a walk, not a trail. With two distinct parallel edges between A and B, using one out and the other back is a circuit.
Step by step
Step 1 / 6
Write a walk
A walk specifies successive adjacent vertices and the edges traversed between them. Repetitions are allowed.
Vertex names alone may be insufficient when parallel edges exist.
Worked example
A triangle ABC has an extra edge AD to a new vertex D. Find an Euler trail.
- Degrees are A=3, B=2, C=2, D=1. A and D are odd.
- D→A→B→C→A uses AD,AB,BC,CA exactly once each.
- A repeats, but no edge repeats: it is a trail, not a path.
Optional self-check
In a single-edge graph A–B, is A→B→A a trail, a circuit, or just a closed walk?
Show answer
It is a closed walk of length 2. The undirected edge AB repeats, so it is not a trail and not a circuit under these definitions.