= Closed walk
{title2=$v_m=v_0$}
A <closed walk> is a <walk> with equal endpoint <vertices>, $v_m=v_0$. Under our convention this includes the zero-length <walk> $(v)$; returning after traversing at least one <edge> requires $m>0$. Closure imposes no other restriction on repeated <vertices> or <edges>. In a <directed graph>, a <closed directed walk> must also follow every <directed edge> in its permitted direction.<Mathematics for Computer Science by Eric Lehman and others>[Lehman, Leighton and Meyer, Mathematics for Computer Science, §§9.2 and 11.8.1: closed walks]{ref}
\Image[/walks-trails-closed-walks-return-comparison.png]
{title=Returning to $A$: backtracking <closed walk>, closed <trail> with a repeated internal <vertex>, and <graph cycle>}
In the shared <simple graph>, $A,F,A$ is a length-two <closed walk> that immediately backtracks along $AF$. It is not a <trail>, since $AF$ is used twice, and it is not a <graph cycle>. The length-six <closed walk> $A,B,C,A,D,E,A$ is a <trail>, since its six <edges> are distinct, but is not a <graph cycle>: it returns to $A$ midway through the journey. The length-three <closed walk> $A,B,C,A$ is a <graph cycle>, with all <vertices> distinct apart from the required endpoint repetition. In a <simple graph> that is an <undirected graph>, a <graph cycle> has length at least three; the two-step backtrack is excluded.<Mathematics for Computer Science by Eric Lehman and others>[Lehman, Leighton and Meyer, Mathematics for Computer Science, §11.8.1: cycles and backtracking]{ref}
A positive-length <closed walk> therefore need not reveal a <graph cycle>: even a <tree> permits an out-and-back journey on an <edge>. A positive-length closed <trail> in a <simple graph> does contain a <graph cycle>. For a proof outline, choose a shortest positive-length consecutive portion of the <trail> whose endpoint <vertices> coincide. It cannot repeat an internal <vertex>, since that would give a shorter such portion; it cannot have length one or two because <self-loops> and repeated <edges> are excluded. It is consequently a <graph cycle>. Cutting it out leaves another closed <trail>, possibly of length zero, so repetition partitions the original <edges> into <graph cycles>. In our six-step example these are the two <triangles in a graph>. A closed <trail> using every <edge> would be an <Euler circuit>; here $AF$ is omitted.
Counting return journeys makes <closed walks> useful even when they repeat <edges>. For a finite <simple graph> with <adjacency matrix> $M$, the <walk count from powers of an adjacency matrix> gives $(M^k)_{uv}$ length-$k$ <walks> from $u$ to $v$, for every <nonnegative integer> $k$. A proof outline is that <matrix multiplication> appends one allowed step, summing over the previous endpoint; $M^0$ is the <identity matrix>, recording the unique zero-length <walk> at each <vertex>. Consequently
$$
(M^k)_{vv}=\#\{\text{length-}k\text{ closed walks starting at }v\},\qquad \operatorname{tr}(M^k)=\sum_{v\in V}(M^k)_{vv}.
$$
The <trace> counts <closed walks> with a specified starting <vertex> and traversal order, not distinct <graph cycles>. These formulas use adjacency entries, not arbitrary travel costs in a <weighted graph>.https://ocw.mit.edu/courses/14-15-networks-spring-2022/mit14_15s22_lec2.pdf[Alexander Wolitzky, Graph Theory and Social Networks, slides 9–10: powers of adjacency matrices]{ref}
In our example, $(M^2)_{AA}=5$: the five length-two <closed walks> are $A,B,A$, $A,C,A$, $A,D,A$, $A,E,A$, and $A,F,A$. Also $(M^3)_{AA}=4$, going round either <triangle in a graph> in either direction, and $\operatorname{tr}(M^3)=12$: each of the two <triangles in a graph> supplies three choices of starting <vertex> and two directions. These exact counts for the constructed <graph> illustrate why return counts and <graph cycle> counts differ.
A <closed walk> naturally models a delivery or inspection journey that returns to its depot. Repeated <vertices> let it combine several excursions; repeated <edges> let it serve a dead end and return. For an <Euclidean travelling salesman tour>, one can first construct a <closed walk> visiting all locations and then use the <triangle inequality> to shortcut repeated visits without increasing total length. That argument assumes direct travel between the retained locations is permitted, as in a <complete graph> weighted by <Euclidean distance>; an arbitrary road network need not contain those shortcut <edges>.
Back to article page
