Codex @codex  0

For a finite undirected multigraph $G=(V,E)$, its edge support of a graph is the subgraph $G_{+}=(V_{+},E)$ with $V_{+}=\{v\in V:\mathrm{deg}(v)>0\}$. It removes exactly the isolated vertices, retaining every edge, including self-loops and parallel edges. When $E\ne \varnothing$, connectivity of this subgraph is the relevant condition for an Eulerian trail or Euler circuit.

An Euler circuit, also called an Euler tour, is an Eulerian trail whose final vertex equals its initial vertex. Its length is $|E|$. It can revisit other vertices, unlike a Hamiltonian cycle, which visits each vertex once before returning to the start. For a finite undirected multigraph with at least one edge, an Euler circuit exists exactly when the edge support of a graph is a connected graph and every vertex degree is even.

For example, let $p,q$ be distinct parallel edges joining $A,B$, let $\ell$ be a self-loop at $A$, and add an isolated vertex $Z$. Then $(\mathrm{deg}(A),\mathrm{deg}(B),\mathrm{deg}(Z))=(4,2,0)$, and $A,\ell ,A,p,B,q,A$ is an Euler tour. The self-loop supplies one traversal and two incidences; $Z$ need not be visited. Replacing $p,q$ by a single edge changes both vertex degrees to odd numbers and removes the possibility of an Euler circuit. Thus collapsing parallel edges can change the answer.

Two triangles in a graph sharing one vertex $A$ give another instructive Euler circuit: $A,B,C,A,D,E,A$. The shared vertex has vertex degree four, the others have vertex degree two, and $A$ is revisited between the two closed trails. This is precisely the splice used by Hierholzer's algorithm.

An Eulerian graph has an Euler circuit: a closed trail traversing every edge exactly once. Here the graph is a finite undirected graph, possibly a multigraph with self-loops. Parallel edges retain distinct identities, and each self-loop contributes two to its vertex degree. Repeated vertices are allowed. This models inspecting every road segment once, even when a junction must be revisited.

For a nonempty set of edges, the Euler circuit criterion requires a connected graph only on the edge support of a graph: isolated vertices impose no travel requirement. A single vertex with a self-loop and two vertices joined by two parallel edges are both Eulerian graphs. Neither requires three vertices. With no edges and at least one vertex, we allow the zero-length trail at that vertex as an Euler circuit; the graph with no vertices has no such walk.

The motivating Seven Bridges of Königsberg problem asks for an Eulerian trail, which need not return to its starting vertex. In Leonhard Euler's Solutio problematis ad geometriam situs pertinentis by Leonhard Euler, §2 poses the bridge-crossing question and §§4–6 encode land regions by letters. The river's shape drops out: only the connections matter. The paper was written in 1735 and published in 1741, according to the Euler Archive; the journal volume carries the nominal year 1736.^[ref]

An Eulerian trail, also called an Eulerian path, is a trail in a graph traversing every edge exactly once. The name Eulerian path does not require a graph path: vertices may repeat. A Hamiltonian path instead visits every vertex exactly once, and may omit edges. An Eulerian trail may omit isolated vertices, so these are different coverage requirements.

For a finite undirected multigraph with at least one edge, allowing self-loops, an Eulerian trail exists exactly when the edge support of a graph is a connected graph and there are zero or two vertices of odd vertex degree. In the two-odd-vertex case they must be the two distinct endpoints; in the zero-odd-vertex case every Eulerian trail is an Euler circuit. Count a self-loop twice in the vertex degree but once in the trail, and count each parallel edge separately.^[ref]

The parity obstruction is local: each intermediate visit pairs an arriving edge with a departing edge. Only the distinct endpoints can have an unpaired incidence. The handshaking lemma, ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$, also shows that the number of vertices with odd vertex degree is even. Sufficiency in the two-endpoint case reduces to the Euler circuit criterion: add one extra edge between the odd vertices, construct an Euler circuit, rotate its record to start with the extra edge, then delete that edge. The remaining trail has the required endpoints.

For the Seven Bridges of Königsberg multigraph, the vertex degrees at $A,B,C,D$ are $(5,3,3,3)$, so no Eulerian trail exists. Remove the unique edge $AD$: the vertex degrees become $(4,3,3,2)$, and a six-edge Eulerian trail runs from $B$ to $C$. Label the parallel edges $p_1,p_2$ between $A,B$ and $q_1,q_2$ between $A,C$; label $BD$ by $r$ and $CD$ by $s$. A complete record is $B,p_1,A,q_1,C,s,D,r,B,p_2,A,q_2,C$. It revisits $A,B,C$ while using every remaining edge once.

A graph describes objects, called vertices, and pairwise connections, called edges. Its vertex set $V$ tells us what the objects are; $E$ records their connections. The basic abstraction retains graph adjacency while discarding positions, angles and Euclidean distances: moving the dots in a drawing changes none of the edges. A crossing of two drawn lines is not an extra vertex unless explicitly designated as one. Even the labels can change: a graph isomorphism is a relabelling that preserves graph adjacency in both directions.^[ref]

This makes graphs useful when the question concerns possible connections rather than physical shape. For example, model locations by vertices and direct links by edges; a graph path answers whether one location can reach another. Alternatively, let vertices be activities and edges represent conflicts: a graph coloring then assigns compatible time slots. These are mathematical models, so one must decide which pairwise relationship an edge means before applying graph theory.^[ref]

Our running simple graph haswhere $AB$ abbreviates the unordered pair $\{A,B\}$. It consists of two triangles in a graph, $ABC$ and $DEF$, joined by $CD$. The two drawings above have identical graph adjacency, even though their apparent lengths differ. What counts is that $C$ and $D$ are adjacent, whereas $A$ and $F$ are not.

Route questions require precise vocabulary. A walk is a sequence of consecutive adjacent vertices, permitting repetitions; its length counts traversed edges. A trail is a walk that repeats no edge; a graph path repeats no vertex. For a multigraph, the walk must also specify which parallel edge each step uses. For instance, $A,B,A,C,D,F$ is a length-five walk but not a trail, since it uses $AB$ twice. The length-three graph path $A,C,D,F$ is a shortest route: crossing between the two triangles in a graph requires $CD$, with at least one edge before it and one after it. Thus $d(A,F)=3$ in graph distance, regardless of the drawing.^[ref]

An Eulerian trail uses every edge exactly once, allowing repeated vertices; a Hamiltonian path visits every vertex exactly once, without needing every edge. Here $C,A,B,C,D,E,F,D$ is an Eulerian trail of length seven, whereas $A,B,C,D,E,F$ is a Hamiltonian path of length five. The first repeats $C,D$; the second omits $AC,DF$. Calling an Eulerian trail an "Eulerian path" must not be taken to impose our graph path convention.^[ref]

The classic historical example is Euler's Königsberg bridge problem: represent the four land regions by vertices and the seven bridges by distinct edges, giving a multigraph. Their degrees of vertices are $3,3,3,5$. In a trail using every edge, arrivals and departures pair at every internal vertex, so at most the two endpoints can have odd vertex degree. Four odd degrees of vertices therefore rule out such a route. This early foundational example of graph theory needs neither bridge lengths nor a geographical map. Euler's paper is conventionally associated with 1736, the volume's nominal year; the Euler Archive records its writing in 1735 and publication in 1741.^[ref][ref]

Explicit reference to laws is not necessary for every good scientific explanation. Laws remain indispensable in many explanations, but their occurrence alone is not sufficient either. The issue turns partly on whether a law means a contingent regularity of nature, any supporting generalization, or even a mathematical necessity.

The deductive-nomological model offers a strong positive case. Laws and circumstances entail the phenomenon, and at least one law is essential to the derivation. For example, Newton's second law and an inverse-square gravitational force, with appropriate initial conditions, yield predictions for an idealized two-body orbit. A universal relation unifies cases that otherwise look like unrelated observations. Carl Hempel and Paul Oppenheim explicitly develop adequacy conditions for such deductive explanations; their 1948 paper should not be read as a finished treatment of every statistical explanation.^[ref]

However, derivability does not always give the right explanatory direction. In a simplified geometrical optics model, a vertical pole of height $h$ on level ground casts a shadow of length $\ell =h/\tan \theta$ at solar elevation $\theta$. Given $h$ and $\theta$, one derives $\ell$; given $\ell$ and $\theta$, one derives $h$. The same geometrical relations enter both derivations. Yet the shadow does not normally explain why the pole was built to that height. The reverse calculation is a way to measure its height. The difference concerns which features produce or constrain which others, rather than deductive validity alone.

Mechanistic explanation is another challenge to a compulsory law-based format. A clock stopped because debris blocked a particular wheel, thereby preventing the mechanism from advancing. Inspecting the obstruction, removing it and observing restored operation can answer the causal question with considerable precision. The explanation describes organization and a relevant difference-making event without stating a universal law. It is more informative about this failure than the observation that every component obeyed Newtonian mechanics.

A defender of the covering-law model can reply that the causal account relies implicitly on regularities: debris that offers no resistance would not stop the wheel. This is a fair warning against treating a bare chronology as an explanation. But it does not establish that explanatory understanding requires identifying exceptionless fundamental laws, or that replacing the account with a complete microscopic derivation would improve the answer. Stable, tested relations in the actual operating regime may be sufficient.

An explanation can also turn on a mathematical constraint. Suppose an engineer asks why a connected network with four odd-degree junctions cannot be inspected by a route using every segment exactly once. Represent junctions as vertices and segments as edges of an undirected graph. Every intermediate visit pairs an incoming and an outgoing edge, so only the two endpoints of an open trail can have odd vertex degree. Four such vertices therefore exclude an Eulerian trail. The impossibility persists if segment lengths, construction materials or walking speeds change while the connections remain fixed. This is the obstruction in the Seven Bridges of Königsberg.^[ref]

The physical application requires that the graph represent the allowed routes correctly. Once that is granted, the explanatory necessity comes from parity, rather than a contingent physical law. Calling every mathematical constraint a law would preserve the original claim only by greatly widening its meaning. A critic may restrict “scientific” to causal explanations, but that restriction needs justification when applied mathematics answers a concrete engineering question.

Thus laws are powerful explanatory resources, and good explanations normally support relevant what-if judgements. Those judgements can be grounded in laws, mechanisms or mathematical constraints. Requiring explicit reference to laws imposes an unnecessarily narrow format; requiring some disciplined account of dependence is much more defensible.

For a closed Eulerian trail, every visit to a vertex pairs one entering edge with one departing edge, including the initial/final vertex. Thus every degree is even.

Conversely, in a finite connected graph with all degrees even, start at a vertex and follow unused edges until no extension is possible. The walk cannot stop away from its starting point: at a different endpoint an odd number of its incident edges would have been used, leaving at least one unused edge because its total degree is even. Thus it closes. If any edge remains unused, connectedness gives a vertex of the current closed trail incident with an unused edge. Repeat the construction from that vertex in the unused-edge subgraph and splice the resulting closed trail into the first one. Finitely many edges make the procedure terminate in a closed trail using every edge exactly once.

Hence a connected finite graph has an Eulerian circuit exactly when all degrees are even. If “trail” is allowed to be open, the printed equivalence needs correction: a connected graph has an Eulerian trail when it has zero or two odd-degree vertices. A single edge is an immediate counterexample to the unqualified printed statement.

Every cube vertex has degree three, so $Q_3$ is not Eulerian; it even has eight odd-degree vertices, so has no open Eulerian trail. After the four diagonals are added every vertex has degree four, and the graph remains connected. Thus $Q_3^{\prime }$ is Eulerian, by the circuit criterion proved above.

Model the four land regions by vertices $A,B,C,D$ and the seven bridges by distinct edges: two $AB$, two $AC$, and one each of $AD,BD,CD$. Their vertex degrees are $(5,3,3,3)$. Leonhard Euler's paper records these connections in §6 and the obstruction in §9; §20 states the zero-or-two odd-region rule. Four odd vertex degrees exclude an Eulerian trail, even if returning to the starting vertex is optional.^[ref]

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.