Can a walk revisit its starting vertex?

Yes. Walks allow repeated vertices, and a walk ending at its start is closed.

Does a length-three walk contain three vertices?

It has four vertex occurrences, though some may repeat.

Is every walk a random walk?

No. Randomness requires an additional rule for choosing transitions.

AI Glossary / Graphs and symbolic AI / Intermediate

Walks

Definition

Walks are sequences of vertices connected by successive edges in a graph. Unlike simple paths, walks may repeat vertices and edges. In a directed graph, each step must follow an edge's direction. A walk's length usually counts its traversed edges, so a length-k walk is represented by k + 1 vertex occurrences, including the starting vertex.

What it means

A walk records a possible sequence of transitions, not necessarily an efficient route. Moving from A to B and back to A is a valid two-edge walk in an undirected graph, even though it returns to its starting point.
Repeated occurrences matter. The sequence A,B,A,B contains four vertex occurrences but only two distinct vertices and has length three. A trail forbids repeated edges, while a simple path forbids repeated vertices. Terminology can vary across sources, so applications should state their conventions rather than using walk and path interchangeably.

How it works

To construct a walk, begin at a vertex and repeatedly choose an adjacent vertex, respecting direction when present. A closed walk finishes where it started. A length-zero walk remains at its starting vertex without traversing an edge; this is different from counting an arbitrary pause as an extra step.
To count fixed-length walks in an unweighted simple graph, use powers of its adjacency matrix. The entry in row u and column v of the kth power counts length-k walks from u to v. Matrix multiplication sums over possible intermediate vertices. Weighted matrices have a different interpretation, and parallel-edge conventions require care when moving beyond simple graphs.

Three practical examples

A graph-analysis lesson can count possible transition sequences of a fixed length between two vertices.
A network model can distinguish a route that revisits a location from a simple path without repetitions.
A random-walk simulation can generate sequences according to transition probabilities, while keeping those probabilities distinct from raw walk counts.

Think of it this way

Think of recording every stop during a walk through connected streets, including returns to places already visited. The record describes the journey even when it loops. The analogy is limited because graph edges may represent abstract transitions, and the number of possible journeys does not determine how likely a person or algorithm is to choose each one.

Worked example

Consider an original simple undirected triangle with vertices A, B, and C and edges AB, BC, and CA. There are no self-loops. Each vertex has two neighbors.
Starting at A, the length-two walks are A - B - A, A - B - C, A - C - A, and A - C - B. Two end at A, one at B, and one at C. The return A - B - A repeats the same undirected edge, which is allowed for a walk but not for a trail.
Now count length-three walks from A to B. They are A - B - A - B, A - B - C - B, and A - C - A - B. There are three. Each sequence has three traversed edges and four vertex occurrences.
There are two length-three walks from A back to A: A - B - C - A and A - C - B - A. By symmetry, there are three from A to C. The total is 2 + 3 + 3 = 8, agreeing with two choices at each of three steps: 2³ = 8.
Using vertex order A,B,C, the adjacency matrix has zeros on its diagonal and ones elsewhere. Its square has diagonal entries two and off-diagonal entries one, matching the length-two counts. Its cube has diagonal entries two and off-diagonal entries three, matching the length-three counts. The identity matrix, the zeroth power, records one length-zero walk from each vertex to itself and none between different vertices.
If a random walker chooses each available neighbor with probability one half, every particular length-three walk has probability one eighth. Its probability of ending at B from A is therefore 3/8. This probability follows from the additional uniform-choice rule. The raw count three alone does not specify a probability for a differently weighted random walk.
Finally, reverse the perspective: A and B are directly adjacent, so their shortest-path distance is one, even though there are three walks of length three between them. Counting fixed-length walks and finding a shortest path answer different questions.

Illustrative case study

In a fictional graph-learning workshop, a team analyzes transition sequences in a small process model. Its first report calls all counted sequences paths, even though some repeatedly revisit the same state.
The team corrects the terminology and states whether repeated transitions are meaningful for the application. It also separates sequence counts from simulated frequencies generated under a probability model. This fictional case illustrates clear interpretation rather than a measured model-performance result.

Common misconceptions and mistakes

A walk need not be simple, shortest, or self-avoiding. Repeating an edge does not invalidate it. However, a directed edge cannot generally be traversed backward unless a reverse edge also exists.
Do not confuse a length-k count with the number of walks of length at most k. Do not interpret weighted adjacency powers as ordinary unweighted counts without checking the weight meaning. A self-loop, when present, is an actual edge traversal; it is different from adding an unmodeled pause. Large fixed-length counts can also grow quickly, so numerical representation matters.

Business use

The distinction is useful whenever a system reasons about sequences of connected states. It helps teams determine whether repeated visits represent valid behavior, unwanted loops, or a different question from simple routing.
Define length, direction, repeat rules, and any probability model before analyzing results. If using an API, check whether edge weights are considered and whether the result counts exact lengths. NetworkX's inspected number_of_walks implementation uses an unweighted adjacency matrix, so ordinary edge-weight attributes do not change those counts.

Check your understanding

Why is A - B - A - B valid even though AB is used repeatedly?

Answer: Repeated edges are permitted in a walk. The sequence would fail the stricter no-repeated-edge requirement for a trail.

Related terms

Path
Simple Paths
Trail
Random walk
Simple path
Closed walk
Adjacency matrix
Matrix power
Shortest-path distance

Learn next

Next, count length-four walks from A back to A in the triangle. Each of the three length-three walks ending at B and each of the three ending at C can return to A, giving six. Explain why the two length-three walks already at A cannot add a one-step stay without a self-loop.

Sources

Primary sources: NetworkX number_of_walks reference: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.walks.number_of_walks.html ; implementation: https://networkx.org/documentation/stable/_modules/networkx/algorithms/walks.html . The triangle enumeration and probability calculation are original.

Previous: Wald - Wolfowitz runs test Next: Ward histogram-based tone mapping