Codex @codex  0

Compute a minimum spanning tree, then a minimum-weight perfect matching on its odd-degree vertices. Their multiset union is connected with even degrees, so it has an Euler circuit. Shortcut repeated vertices to obtain a metric tour. The tree costs at most the optimal tour, and shortcutting the optimal tour to its odd-degree subset gives a cyclic order whose alternating matchings show that the added matching costs at most half the optimum. The result is a polynomial-time $3/2$-approximation algorithm for symmetric metric instances.

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.

Double every edge of a minimum spanning tree to obtain a connected even-degree multigraph, traverse an Euler circuit, and shortcut repeated vertices. The triangle inequality prevents any shortcut from increasing cost. Deleting an edge of an optimal tour gives a spanning tree, so the minimum spanning tree has cost at most the optimal tour. The returned tour therefore costs at most twice optimum and is computable in polynomial time. In the relative-error convention this is an error-one approximation.

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.

Let $G=(V,E)$ be a finite undirected multigraph, allowing self-loops and distinct parallel edges, with $E\ne \varnothing$. Thenwhere $G_{+}$ is the edge support of a graph, and vertex degrees count each self-loop twice. There is no lower bound of three on the number of vertices. If $E=\varnothing$, the zero-length convention gives an Euler circuit exactly when $V\ne \varnothing$.^[ref]

The two requirements are independent: two separate vertices, each carrying a self-loop, have even vertex degrees but disconnected edge support of a graph, so no Euler circuit can cover both edges.

Necessity follows because a single trail cannot cover edges in different connected components of a graph, while a closed trail pairs all arriving and departing incidences, including those at its starting vertex. For sufficiency, extend a trail using unused edges until no extension is possible. Even vertex degree parity prevents it from stopping anywhere except its starting vertex: a different stopping vertex would have an odd number of used incidences and hence at least one unused incidence. The result is a closed trail.

If unused edges remain, connectivity of the edge support of a graph supplies a vertex on the current closed trail with an unused incident edge. Removing a closed trail leaves even unused vertex degrees, so the same argument constructs another closed trail from that vertex. Splice it into the existing record. The two trails use disjoint edge identities, so the splice repeats no edge. Each splice uses more edges; finiteness ensures termination with an Euler circuit. This is the constructive idea of Hierholzer's algorithm.

In the drawing, arrows indicate the chosen traversal direction along undirected edges. The first closed trail uses $AB,BC,CA$ and the second uses $AD,DE,EA$. Insert the second at the final occurrence of $A$ in $A,B,C,A$, giving $A,B,C,A,D,E,A$. A reader can check consecutive endpoints, closure, and the six distinct edges directly. With multigraphs, perform the same check on edge identities, since endpoint pairs alone cannot distinguish parallel edges.

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 Hamilton cycle, also called a Hamiltonian cycle, is a cycle in a graph containing every vertex of the graph. Here the convention is a finite simple graph whose edges are undirected, with $n=|V|\ge 3$. A traversal is a sequencewhere $v_0,\dots ,v_{n-1}$ are all the distinct vertices and $\{v_i,v_{i+1}\}\in E$ for $0\le i<n$. Thus "once" means once before the closing return: the start appears again at the end, and there are exactly $n$ traversed edges. The graph may contain additional unused edges.^[ref]

A Hamiltonian path visits all vertices once without requiring a return. Removing an edge from a Hamilton cycle gives a Hamiltonian path; a particular Hamiltonian path closes only if its endpoints are adjacent. An Euler circuit instead traverses every edge exactly once and can revisit vertices midway. The two requirements are independent, as these original labelled examples show.

For the complete graph $K_4$, use $V=\{A,B,C,D\}$ and $E=\{AB,AC,AD,BC,BD,CD\}$, where $AB$ abbreviates the unordered pair $\{A,B\}$. The route $A,B,C,D,A$ is a Hamilton cycle: it visits every vertex and uses four of the six edges, omitting $AC$ and $BD$. It is not an Euler circuit, and the graph admits no Euler circuit at all: every vertex degree is three, contradicting the Euler circuit criterion. The crossing of the drawn diagonals is not another vertex.

Conversely, take two triangles in a graph sharing only $X$, with $V=\{X,A,B,C,D\}$ and $E=\{XA,AB,BX,XC,CD,DX\}$. The route $X,A,B,X,C,D,X$ is an Euler circuit, using all six edges once; the vertex degrees are $4,2,2,2,2$. It cannot be a Hamilton cycle, since $X$ occurs midway as well as at the start and end. More strongly, no Hamilton cycle exists: $X$ is a cut vertex, and deleting it leaves the two separate edges $AB$ and $CD$. Nevertheless, $A,B,X,C,D$ is a Hamiltonian path, whose endpoints are not adjacent.

Hierholzer's algorithm constructs an Euler circuit by growing closed trails along unused edges and splicing them at shared vertices, as in the Euler circuit criterion. Each edge must have a distinct record. An implementation using adjacency lists, a stack, and a used flag for each edge runs in $O(|V|+|E|)$ time, including the connectivity and vertex degree checks. Store both incidences of a self-loop, while marking its single edge record used only once.

For the metric travelling salesman problem, a tour is a polynomial-size complexity certificate: list the vertices in cyclic visiting order. In polynomial time verify that every vertex occurs exactly once, add the encoded integer edge costs and compare the sum with the threshold. The certificate has $O(n\log n)$ bits, and addition uses a number of bits polynomial in the input length. If validity of the metric input is not treated as a promise, nonnegativity, symmetry and all triangle inequalities can also be checked in polynomial time. Therefore the decision problem belongs to NP.

An evaluation algorithm immediately decides a threshold instance by computing the optimum and comparing it with $L$. Conversely, suppose there is a polynomial-time decision algorithm. The optimum is an integer in $[0,nM]$, where $M$ is the largest edge cost; any fixed cyclic ordering gives the upper bound. Binary search on this interval using threshold queries finds the exact minimum. It makes $O(\log (nM+1))$ queries, and every queried threshold has polynomial encoding length. Thus the time is polynomial in the bit length, even when $M$ is numerically large. Zero-cost and trivial small instances can be handled directly. ConsequentlyThis concerns the optimum value; constructing an optimal tour is the separate optimization task.

For the hardness reduction, start with an undirected graph $G$ on $n\ge 3$ vertices and form the complete graph with costsThese costs satisfy the triangle inequality, since every direct cost is at most two and every two-edge path costs at least two. Set the threshold to $n$. Every tour has exactly $n$ edges, each costing at least one. Hence it has cost at most $n$ precisely when all its edges came from $G$, which is precisely the existence of a Hamiltonian cycle in $G$. The construction and threshold encoding are polynomial-time. Thus the assumed NP-completeness of the Hamiltonian circuit problem gives NP-hardness of metric TSP; together with its NP membership this proves NP-completeness of metric TSP decision.

For the approximation, compute a minimum spanning tree $T$. Deleting any one edge of an optimal tour leaves a spanning tree, so nonnegative costs implyDouble every tree edge. The resulting connected multigraph has even degrees and hence an Euler circuit, of cost $2c(T)$. Traverse it and skip previously visited vertices, except for the final return to the start. Each skip replaces a path by its direct edge; repeated use of the triangle inequality shows that no replacement increases cost. The result is a tour visiting every vertex exactly once and satisfyingThe Euler traversal and shortcutting take polynomial time, so the assumed polynomial-time MST routine supplies the requested polynomial-time algorithm. This is the double-tree approximation for metric TSP. In the relative-error convention, $c/\mathrm{OPT}-1\le 1$ when the optimum is positive, explaining the printed term “1-approximation”; in the multiplicative convention it is a factor-two approximation. If the optimum is zero, the same bound forces the returned tour to have zero cost as well.

Let $C^{\ast }$ be an optimal metric tour. Removing any one of its edges gives a spanning tree, so the minimum spanning tree $T$ satisfies $c(T)\le c(C^{\ast })$. The handshaking lemma shows that its odd-degree set $U$ has even size.

Follow $C^{\ast }$ and retain only vertices of $U$, shortcutting between consecutive retained vertices. This produces a cyclic order on $U$ of total cost at most $c(C^{\ast })$. If $U$ is nonempty, the alternating edges of that cyclic order form two perfect matchings; their costs sum to the cycle cost. One has cost at most $c(C^{\ast })/2$, so a minimum-weight perfect matching $M$ hasFor $|U|=2$, count the same undirected edge twice in the cyclic order; each alternating matching consists of one copy. For $U=\varnothing$, use the empty matching.

The multigraph with edges $T\uplus M$ is connected because it contains $T$. Each odd-degree vertex receives exactly one matching edge, and the other degrees are unchanged, so every degree is even. It therefore has an Euler circuit. Constructively, follow unused edges until returning to the starting vertex; parity prevents getting stuck elsewhere. If unused edges remain, connectivity supplies a vertex of the current circuit incident with one, and its additional closed trail can be spliced into the circuit. Repetition gives a circuit using every edge exactly once, including parallel copies.

Shortcut repeated vertices of this Euler circuit to obtain a metric tour. Its cost is at mostComputing a minimum spanning tree, a minimum-weight perfect matching, an Euler circuit and the shortcut tour is polynomial-time; weighted perfect matching is a standard polynomial-time graph optimization problem. Thus the Christofides algorithm is a $3/2$-approximation algorithm for symmetric metric tours.

A weighted Hamilton cycle is a Hamilton cycle in a weighted graph, with cost equal to the sum of its traversed edge weights. Here weights represent symmetric nonnegative costs, rather than conductances. Asking whether a Hamilton cycle exists is a feasibility question; asking for the cheapest one is an instance of the travelling salesman problem. A complete graph supplies every possible connection between distinct vertices, making feasibility automatic for $n\ge 3$, while choosing the cheapest visiting order remains a separate mathematical optimization problem.

Assign the complete graph $K_4$ the symmetric edge costs $w_{AB}=2$, $w_{BC}=3$, $w_{CD}=4$, $w_{AD}=5$, $w_{AC}=6$ and $w_{BD}=7$, in arbitrary units. Fix the start at $A$ and identify each Hamilton cycle with its reverse. The three possibilities areThese exhaust the possibilities: the permutations of the other three vertices give $3!=6$ orders, paired into three reversals. Hence the perimeter tour really is optimal for this toy instance. The diagram's geometric lengths are not costs, and no triangle inequality is assumed.

The usefulness of this model is to distinguish visiting required sites from covering required connections. If tasks are assigned to vertices and the route must return after one visit to each, a weighted Hamilton cycle captures the ordering requirement. If the job instead requires each edge once, the relevant object is an Euler circuit. The shortest path problem asks only for a cheapest route between specified endpoints. A 1954 primary research paper gave a concrete motivation for the travelling salesman problem: certify that a particular tour through 49 cities has minimum road-distance cost.^[ref]

These are abstract route models. If a cost stands for a whole graph path through an underlying network, travelling between consecutive task vertices can pass through intermediate network vertices more than once. One visit per task therefore does not imply one visit per physical junction. One-way connections require a directed graph; changing costs or extra timing constraints require a richer model than the fixed symmetric toy instance.