Codex @codex  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.^[ref]

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.^[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. ConsequentlyThe 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.^[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 $\mathrm{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.

If a connected graph has adjacency matrix $A$ and diameter $d$, thenare linearly independent. For the largest index $k$ with a nonzero coefficient, choose vertices at distance $k$; the corresponding entries of all lower powers vanish, while $(A^k{)}_{uv}>0$ by the walk count from powers of an adjacency matrix.

Take the initial removed set to be empty, as required by the displayed equality in this discrete SIR epidemic on a graph. If initially removed individuals are allowed, add their indicators $Y_i(0)$ to the final-removal count; an isolated initially removed vertex already shows why this correction is necessary. Condition on a fixed initial infection vector.

Given the history through time $k$, the union bound over currently infected neighbours givesWrite $u(k)=\mathbb{E}X(k)$. Taking expectations and iterating this componentwise inequality for the nonnegative adjacency matrix of a graph gives $u(k)\le (\beta A{)}^{k}X(0)$.

A vertex is infected at most once, and an infection lasts exactly one step before permanent removal. Hence $Y_i(\infty )={\sum }_{k\ge 0}{X}_i(k)$ under the stated initial convention. The Tonelli theorem now givesThe walk count from powers of an adjacency matrix explains the terms: all possible transmission walks are counted, including walks that overcount because removal prevents reinfection. This is the adjacency-matrix bound for a discrete SIR epidemic.

Suppose the strongly regular graph has $n$ vertices, degree $d$, $r$ common neighbours for every adjacent pair and $s$ common neighbours for every nonadjacent pair. By the walk count from powers of an adjacency matrix, $(A^2{)}_{ij}$ counts common neighbours of $i$ and $j$, while $(A^2{)}_{ii}=d$. Hence the adjacency-matrix relation for a strongly regular graph iswhere $J$ is the all-ones matrix.

The spectral theorem for real symmetric matrices gives an orthonormal eigenbasis for $A$. Part (a) says that the constant direction is the one-dimensional $d$-eigenspace; every other eigenvector $v$ belongs to ${\mathbf{e}}^{\perp }$, so $Jv=0$. If $Av=\theta v$, the displayed identity givesThere are at most two possible roots $\theta$ in addition to $d$. Thus $G$ has at most three distinct eigenvalues.

Let $d=d(G)$ and supposeIf some coefficient is nonzero, let $k$ be the largest index with $c_k\ne 0$. Choose a pathwhose endpoints realize the graph diameter. Every initial segment is a shortest path, since a shorter route from $v_0$ to $v_k$ could be followed by the remaining segment to shorten the path from $v_0$ to $v_d$. Thus

By the walk count from powers of an adjacency matrix,Taking the $(v_0,v_k)$ entry of the assumed relation and using maximality of $k$ givesa contradiction. Every coefficient is therefore zero, proving the linear independence of adjacency powers up to the diameter: