Codex @codex  0

Replace each corner of a polygonal schema by a small closed interval cutting across that corner. The endpoint identifications induced by paired polygon edges glue these intervals into a graph at each vertex equivalence class. This is its vertex link. A circle link gives a disc neighbourhood; a closed interval link gives a half-disc neighbourhood in a surface with boundary.

For a complete pairing of the sides of a single polygon, every link endpoint is paired exactly once. In each vertex equivalence class the link graph is connected, since the corner endpoint identifications generate precisely that class, and all its vertices have degree two. It is therefore a circle. For partial pairings, a connected link can instead be a closed interval when it has two unpaired endpoints. Counting free polygon edges alone does not count boundary components of a surface; their endpoints must first be identified.

A corner of a polyhedron, stored with its spatial coordinates and incidences with boundary edges and faces. In a closed manifold boundary representation, the incident faces form a single cyclic fan. The vertices of a polyhedron and edges define a graph, but geometric embedding and valid face incidence require additional information.

The vertex set is the underlying set $V$ of a graph or hypergraph. In a hypergraph, its hyperedges are subsets of this set; in a simple graph, edges are two-element subsets.

A graph whose automorphisms act transitively on its vertices: any chosen vertex of a graph can be carried to any other by a symmetry preserving adjacency. Consequently rooted self-avoiding walk counts are independent of the chosen root.

A walk records a journey through a graph as a finite alternating sequencewhere each edge $e_i$ joins the consecutive vertices $v_{i-1}$ and $v_i$. Both vertices and edges may repeat. Its length is $m$, counting edge traversals with repetitions, rather than counting different edges or measuring the drawing. Here a graph path means a walk with no repeated vertices; a trail instead forbids repeated edges. These conventions distinguish a journey's record from the subgraph consisting of the connections it used.^[ref]

Unless stated otherwise, the examples below use a finite simple graph that is an undirected graph, so an edge may be traversed in either direction. In a multigraph, retain each edge's individual identity as well as its endpoint vertices: two parallel edges are different choices for the same step. If self-loops are allowed, traversing one leaves the current vertex unchanged but adds one to the length. In a directed graph, each step must follow its directed edge from its initial to its terminal vertex, giving a directed walk; reversing a journey need not be possible.^[ref]

We allow the zero-length walk $(v)$ at every vertex $v$. It uses no edges, so it is also a trail and a graph path, and its coinciding endpoints make it a closed walk. This means staying put is a legitimate journey; a graph with no vertices has no such walk. Positive-length restrictions will be stated explicitly.^[ref]

Use the same constructed graph throughout these three sections:Here $AB$ denotes the unordered pair $\{A,B\}$, and $CA=AC$. Two triangles in a graph, $ABC$ and $ADE$, share $A$, with one extra edge $AF$. These are schematic connections, not measured roads; the highlighted connections in the diagram show which edges are used, while the numbered sequence records their order.

The length-six walk $B,C,A,B,C,A,F$ uses $BC$ and $CA$ twice, so it is not a trail. The length-six trail $B,C,A,D,E,A,F$ returns to $A$ but uses six different edges, so it is not a graph path. The length-three graph path $B,C,A,F$ repeats neither vertices nor edges. Thusfor this particular graph. The restrictions answer different routing questions: revisiting a junction is harmless for many journeys, whereas reusing a serviced road segment can matter for an inspection route. Travel costs require a weighted graph; a walk's cost adds the weight of each traversal, even when an edge is used again.

Every finite walk from $s$ to $t$ contains a graph path from $s$ to $t$ after deleting detours. For a proof outline, if $v_i=v_j$ with $i<j$, delete the intervening closed walk. The retained steps still meet at the same vertex, and the length strictly decreases. Repeating terminates with no repeated vertices, or with the zero-length graph path when $s=t$. This explains why reachability can be formulated using either walks or graph paths. With nonnegative edge weights, deletion also cannot increase cost, connecting the argument to the shortest path problem; with negative weights that cost conclusion fails.^[ref]

For every $\epsilon >0$, all sufficiently large finite graphs admit a set partition into at most $M(\epsilon )$ nonempty cells, each of size at most $\epsilon n$, with the displayed ordered irregular-pair weight bound. Start with small cells. Use regularity energy including diagonal rectangles, refine simultaneously by the witness subsets of all irregular pairs, and apply the refinement variance identity for regularity energy. Each failing round raises energy by more than ${\epsilon }^5$, while energy lies in $[0,1]$. The recurrence $k\mapsto k{2}^k$ bounds the final cell count. Equitability is unnecessary for this weighted version.

For a port-labeled $D$-regular graph $G$ and a $d$-regular graph $H$ on its $D$ port labels, replace every vertex by a copy of $H$. An edge makes a step in $H$, crosses the corresponding edge of $G$, then makes another step in $H$. The result has $|G|D$ vertices and degree $d^2$. Its normalized operator is $BRB$, where $B=I\otimes P_H$ and $R$ is the involutive edge rotation of $G$. Decomposing a mean-zero vector into cloud-constant and cloud-orthogonal parts proves the bound $\rho (G\mathrm{zigzag}H)\le \rho (G)+2\rho (H)+\rho (H{)}^2$.