Codex @codex  0

A proper edge colouring gives different labels to any two distinct edges sharing a vertex. We work with finite undirected graphs without self-loops; distinct parallel edges in a multigraph must also have different colours. For a simple graph, whose edges are two-element sets, the condition isEvery colour class $M_i=\{e\in E(G):c(e)=i\}$ is a matching in a graph. Conversely, a set partition of the edges into matchings in a graph supplies a proper edge colouring. Thus minimizing colours means grouping all the edges into as few matchings in a graph as possible.

The line graph makes the relationship with proper vertex colouring explicit: replace each original edge by a vertex, joining two new vertices exactly when their original edges share an endpoint. A proper edge colouring of $G$ becomes a proper vertex colouring of its line graph $L(G)$, so $\chi \prime (G)=\chi (L(G))$. For a multigraph, retain a distinct new vertex for each parallel edge.^[ref]

A shortest-path predecessor $\pi (v)$ records the previous vertex on a chosen route from source $s$ to $v$. When edge relaxation strictly improves $d(v)$ through $u\to v$, set $\pi (v)=u$. For a multigraph, store the actual directed edge, since two edges with the same endpoints can have different weights. Initialize all vertices, including the source, without a shortest-path predecessor. The authored implementation reconstructs a route by following these incoming edges backwards, then reversing their order.^[ref]

At the end of the edge relaxation trace, $\pi (t)=a$, $\pi (a)=b$, and $\pi (b)=s$. Following them gives $t,a,b,s$, so the forward directed path is $s\to b\to a\to t$, of cost $2-1+2=3$. This makes the distance useful: a number tells us the best cost, whereas the shortest-path predecessors tell us which connections to take. In the Dijkstra algorithm, reconstruct a destination's shortest route after its label becomes permanent. In a label-correcting shortest-path algorithm, wait for convergence and the appropriate negative-cost directed cycle check. During correction, a predecessor's label may have changed since its child's last update: immediately after $b\to a$ in the trace, the current chain to $t$ costs $3$ although $d(t)$ still records the earlier discovered route of cost $8$.

Strict improvement is a useful guard against directed cycles in the recorded pointers. Consider $s\to a$ and $s\to b$ of cost zero, followed by $a\to b$ and $b\to a$, also of cost zero. After the first two edge relaxations, both labels are zero and both shortest-path predecessors are $s$. If equality also allows pointer replacement, the last two operations can set $\pi (b)=a$ and $\pi (a)=b$: following pointers loops forever despite correct distance labels. Keeping the old pointer on ties prevents this example; choosing among equal-cost routes requires a separate rule that preserves a route to the source. Strict improvement alone does not protect against reachable negative-cost directed cycles, which can force endless decreases. Equality on recorded edges plus the Bellman inequalities certifies route costs only when the pointer chains actually terminate at the source.

For all-to-one distances to $r$, record a next vertex $j$ whenever relaxing $i\to j$ improves $d_i$. Follow these successors forward in the original directed graph to reach $r$. They are shortest-path predecessors when viewed in the reversed directed graph; keeping the direction convention explicit prevents returning a route whose arrows point the wrong way.

An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of $C$ is $\Gamma (C)=\{A,B,D\}$, so its degree of a vertex is $\mathrm{deg}(C)=3$. In label order $A,B,C,D,E,F$, the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is $14/6=7/3$. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish $u\to v$ from $v\to u$, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another $CD$ would raise $\mathrm{deg}(C)$ and $\mathrm{deg}(D)$ to four without adding a new neighbour. A self-loop at $A$ contributes two to its undirected vertex degree, making it four, because both endpoints lie at $A$. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.

A trail is a walk whose edge sequence $e_1,\dots ,e_m$ has no repetitions. Its vertices may repeat, including its first and last vertices. The zero-length walk is a trail because it repeats no edge. Every graph path is a trail, but the converse fails: the trail in the shared example isIts six edges $BC,CA,AD,DE,EA,AF$ are pairwise distinct, although $A$ occurs twice. Visiting a junction again and traversing a road segment again are different events.^[ref]

In an undirected graph, traversing $AB$ and then $BA$ repeats the same edge; direction of travel does not give it a new identity. In a multigraph with distinct parallel edges $p,q$ joining $X$ and $Y$, the closed walk $(X,p,Y,q,X)$ is a trail, whereas $(X,p,Y,p,X)$ is not. Both have the same vertex sequence $X,Y,X$. In a directed graph, separate directed edges $X\to Y$ and $Y\to X$ may instead be used once each; record their identities and obey their directions. Thus testing a trail means checking the actual edge records, not merely checking consecutive endpoint labels.

For a finite graph, a trail has length at most $|E|$; unrestricted walks can have arbitrarily large length whenever a positive-length closed walk exists, since it can be repeated. An Eulerian trail is the special trail that uses every edge, so its length is exactly $|E|$. Our length-six trail omits $AB$ and is therefore not an Eulerian trail. In a road-inspection model, a trail describes servicing its selected segments once while allowing returns to junctions; requiring service of every segment leads to the Eulerian trail question. If extra travel between serviced segments is necessary, the complete journey can be a walk even when each segment is serviced only once. This distinction keeps the service requirement separate from the route actually travelled.

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]