Walks, Trails and Circuits

definitions
discrete-math
graph-theory

A walk is a way of getting around a graph: start at a vertex and keep moving along edges. A trail is a walk that never uses an edge twice, and a circuit is a trail that finishes where it started. The difference that matters is edges versus vertices: a trail may come back to a vertex it has already visited, as long as it leaves along a new edge. The last definition here, connected, says that a walk can get from any vertex to any other. These words are what euler-circuits-and-trails and trees are built from. Graphs, degree and the rest of the basic vocabulary are in graphs. First met in 2026-10-26-walks-trails-and-circuits.

Walks

A walk is a sequence \[v_0\, e_1\, v_1\, e_2\, v_2 \cdots v_{i-1}\, e_i\, v_i \cdots e_{n-1}\, v_{n-1}\, e_n\, v_n\] where each \(v_i\) is a vertex, and each \(e_i\) is an edge with endpoints \(v_{i-1}\) and \(v_i\).

It alternates vertex, edge, vertex, edge, …, and starts and ends with a vertex. Each edge joins the vertex before it to the vertex after it. This is a walk from \(v_0\) to \(v_n\), and it has \(n\) edges, counted with repeats.

  • Anything can repeat. A walk can go back along the edge it just used, and pass through the same vertex many times.
  • A walk can have no edges. With \(n = 0\) the walk is the single vertex \(v_0\). That is a walk from \(v_0\) to itself.
  • A loop can be used. If \(e\) is a loop at \(v\), its endpoints are \(v\) and \(v\), so \(v\, e\, v\) is a walk.
  • Why the edges are written in. If two vertices are joined by multiple edges, the vertices alone do not say which edge was used. In a simple graph two vertices are joined by at most one edge (graphs), so the vertices determine the edges and a walk can be written \(v_0 v_1 \cdots v_n\), or \(a, b, c, \dots\).

Trails

A trail is a walk where \(e_1, e_2, \dots, e_n\) are pairwise distinct.

No edge is used twice. That is the only condition. Vertices may repeat: a trail can come back to a vertex it has visited before, provided it arrives and leaves along edges it has not used yet. Every trail is a walk; a walk that uses some edge twice is not a trail.

Circuits

A circuit is a trail \(v_0\, e_1\, v_1\, e_2 \cdots v_{n-1}\, e_n\, v_n\) where \(v_0 = v_n\).

A circuit is a trail that finishes where it started. Like any trail it uses no edge twice, and it can pass through other vertices more than once.

A trivial circuit is a circuit consisting of a single vertex and no edges.
A non-trivial circuit is a circuit that has edges.
A graph is circuit-free if there are no non-trivial circuits.

Every vertex \(v\) gives a trivial circuit, the walk \(v\) with \(n = 0\): it is a trail (it has no edges to repeat) and it starts and ends at \(v\). Every graph has these, so “circuit-free” has to mean free of the non-trivial ones.

The smallest non-trivial circuits:

  • One edge: a loop \(e\) at \(v\) gives the circuit \(v\, e\, v\). An ordinary edge \(e\) joining \(v\) and \(w\) does not give one, because \(v\, e\, w\, e\, v\) uses \(e\) twice.
  • Two edges: two edges \(e_1, e_2\) that both join \(v\) and \(w\) give the circuit \(v\, e_1\, w\, e_2\, v\).
  • In a simple graph there are no loops and no multiple edges, so a non-trivial circuit has at least 3 edges. A triangle \(a\, b\, c\, a\) is the smallest.
Edge repeated? Vertex repeated? Ends where it starts?
Walk allowed allowed allowed, not required
Trail no allowed allowed, not required
Circuit no allowed yes

Figure 1: The three definitions on one graph, with the route in red and arrows showing the direction of travel. Left: a walk that is not a trail, since it uses \(e_1\) twice, drawn as the doubled red line. Middle: a trail that is not a circuit. It visits \(v_3\) twice, arriving along \(e_7\) and \(e_3\) and leaving along \(e_6\) and \(e_2\), but uses every edge at most once, and it ends at \(v_2\), not at \(v_1\) where it started. Right: a circuit. It also passes through \(v_3\) twice, uses no edge twice, and returns to \(v_1\).

Two things about circuits used later, in the proofs in euler-circuits-and-trails:

  • A circuit can be started anywhere on it. If \(v_0\, e_1\, v_1 \cdots e_n\, v_n\) is a circuit and \(1 \le k \le n\), then \[v_k\, e_{k+1}\, v_{k+1} \cdots e_n\, v_n\, e_1\, v_1 \cdots e_k\, v_k\] is a circuit too. Since \(v_n = v_0\), each edge still joins the vertices beside it, it uses the same edges, and it starts and ends at \(v_k\).
  • A circuit can be read backwards. \(v_n\, e_n\, v_{n-1} \cdots e_1\, v_0\) is a circuit with the same edges.

Connected

A graph is connected if and only if there is a walk from any given vertex to any other given vertex.

A graph that is not connected is disconnected: there are two vertices with no walk from one to the other. A drawing of a disconnected graph falls into separate pieces with no edge between them.

  • A graph with one vertex is connected. There is no other vertex to reach.
  • An isolated vertex disconnects a graph with two or more vertices. A walk from it would have to start along an edge, and it has none.
  • A crossing in a drawing is not a connection. Two lines that cross without a dot do not meet, so a drawing that looks like one piece can be a disconnected graph.

To check, pick a vertex, mark every vertex that can be reached from it along edges, then everything reachable from those, and so on. The graph is connected exactly when every vertex ends up marked.

Figure 2: Two graphs with the same degrees, six vertices of degree 2 each. Left: one circuit through all six vertices, a connected graph, since from any vertex there is a walk to any other around the circuit. Right: two separate triangles, a disconnected graph. There is no walk from \(x\) to \(y\), since every walk from \(x\) stays inside its triangle. So the degrees alone do not decide whether a graph is connected.

Common mistakes

  • Thinking a trail cannot revisit a vertex. A trail can pass through a vertex as often as it likes. It is the edges that may not repeat.
  • Thinking a circuit cannot revisit a vertex. Same again: the circuit in the figure above passes through \(v_3\) twice.
  • Going out and back along one edge and calling it a circuit. \(v\, e\, w\, e\, v\) ends where it starts, but uses \(e\) twice, so it is not a trail and not a circuit. It is only a walk.
  • Forgetting the trivial circuit. A single vertex with no edges is a circuit. That is why circuit-free is defined by having no non-trivial circuits.
  • Reading a crossing as a vertex. Only dots are vertices, so lines that cross do not join two pieces of a graph.

See also