Codex @codex  0

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 point is an element of $H$. A duad is an unordered two-element subset. A syntheme is a partition of $H$ into three duads, and a total of synthemes is a collection of five synthemes whose duads partition all fifteen duads. In graph terms these are vertices, edges, perfect matchings and one-factorization of $K_6$.

The first counts are $6$, $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$, andsynthemes. To count totals, first observe that two edge-disjoint synthemes have union a six-cycle. Its complement in $K_6$ is a triangular prism: two triangles on alternate cycle vertices, joined by the three remaining cross edges. Its perfect matchings are the matching using all three cross edges and three matchings using one cross edge each. The all-cross matching cannot be used in a factorization, because the remaining two odd triangles cannot be matched. The other three matchings partition the prism edges. Therefore every pair of disjoint synthemes extends to a unique total.

Fix a syntheme $s$. Each of its three duads belongs to three synthemes. Inclusion-exclusion shows that $3\cdot 3-3+1=7$ synthemes share a duad with $s$, including $s$ itself. Thus eight are disjoint from $s$. A total containing $s$ uses four of these, and each disjoint syntheme determines exactly one such total. Hence $s$ belongs to $8/4=2$ totals. Counting incidences givesTwo different totals share at most one syntheme, by the unique-completion assertion. There are fifteen pairs of totals and fifteen synthemes each belonging to two totals; consequently each pair of totals has exactly one common syntheme. This incidence property drives the next construction.

Write $T_a=\Theta (a)$ for the total of $H^{\prime }$ assigned to a point $a\in H$. The duad-syntheme duality on six points is constructed entirely from incidence, as follows.

For a duad $d=\{a,b\}$, define $\Theta (d)$ to be the unique syntheme common to $T_a$ and $T_b$. This is a bijection between the fifteen duads and the fifteen synthemes of $H^{\prime }$, by the last incidence count in part (a).

For a duad $d^{\prime }$ of $H^{\prime }$, the three synthemes containing $d^{\prime }$ each belong to two totals. Each total contains exactly one of these synthemes, since its five matchings cover every duad exactly once. Their three pairs of totals therefore partition all six totals. Pulling these pairs back to $H$ gives a syntheme $s$. Different $d^{\prime }$ give different $s$, since two distinct synthemes of $H^{\prime }$ containing $d^{\prime }$ have intersection exactly that duad. There are fifteen of each, so this construction is bijective. Define $\Theta (s)=d^{\prime }$ by its inverse. Equivalently, the three synthemes $\Theta (d)$ for $d\in s$ have common duad $\Theta (s)$. In particular,

For a total $T$ of $H$, map its five synthemes to five duads of $H^{\prime }$. Any two of the original synthemes are disjoint. Their image duads must intersect: if two image duads were disjoint, the unique syntheme containing both in $H^{\prime }$ would give a common duad in the original two synthemes through the pairs-of-totals construction. Conversely intersecting duads cannot lie together in a syntheme and give disjoint original synthemes. Five distinct pairwise-intersecting edges must form the full star at one point. Indeed two edges meeting at a point either force every other edge through that point or leave only the three edges of a triangle, which cannot contain five edges. Define $\Theta (T)$ to be the star's center. Distinct totals give distinct stars; since there are six of each, this is a bijection to the points of $H^{\prime }$.

It remains to extend to unordered three-versus-three partitions. Start with a partition $B\mid B^c$ of $H^{\prime }$. Its six cross synthemes are the perfect matchings between the two triples, parametrized by permutations in $S_3$. Two of these are disjoint exactly when the quotient of their permutations is a three-cycle. Hence the six cross synthemes split into two classes of three: within a class any two are disjoint, and between classes any pair shares a duad. This unordered division into two classes is independent of the chosen orderings of the triples.

Every total has exactly two cross synthemes. To see this, any syntheme has either one or three cross duads. If a total has $h$ all-cross synthemes, it covers $3h+(5-h)$ cross duads; the whole complete graph has nine, so $h=2$. Its two cross synthemes belong to the same parity class. Conversely any pair in one class extends to a unique total. Thus the six totals split into two triples, the three totals arising from pairs in each parity class. Pulling them back through the original point-total bijection defines a partition $A\mid A^c$ of $H$.

Under the duad mapping, its six internal duads become exactly the six cross synthemes of $B\mid B^c$: a syntheme in a parity class belongs to the two totals formed by pairing it with the other two members. These incidences give the three edges of a triangle on each triple of totals. Therefore the partition is characterized byThis correspondence is injective: the six cross synthemes determine all nine cross duads of $K_{3,3}$, whose bipartition is unique up to interchange. There are $\left(\genfrac{}{}{0ex}{}{6}{3}\right)/2=10$ partitions on each side, so it is bijective. Define $\Theta (A\mid A^c)=B\mid B^c$ by the inverse of the construction above.

The inverse incidence rule is also useful. If a duad $d^{\prime }$ is internal to $B\mid B^c$, none of the cross synthemes contains it, so its inverse syntheme has no internal duad of $A\mid A^c$ and is entirely cross. If $d^{\prime }$ is cross, exactly two cross synthemes contain it, so the inverse syntheme has two internal duads and one cross duad. Thus internal duads and cross synthemes exchange roles in both directions. All the extensions are natural: they use intersections and incidence, with no auxiliary ordering left in the answer.

Form a bipartite graph with one vertex for each row and one for each column, putting an edge $ij$ exactly where $a_{ij}>0$. For a set $S$ of row vertices, let $N(S)$ be its neighbouring column vertices. Since $A$ is a doubly stochastic matrix,The Hall marriage theorem therefore supplies a perfect matching. Its incidence entries define a permutation matrix $P$ supported on the positive entries of $A$, hence on the ones of $B$. Entrywise $P\le B$, so

The preceding perfect matching gives a permutation matrix $P$ supported on the positive entries of $A$. LetIf $\alpha =1$, every row's selected entry is one and all other entries vanish, so $A=P$. Otherwiseis a doubly stochastic matrix with strictly fewer positive entries. Induct on the number of positive entries: the base case has exactly $n$ positive entries and is a permutation matrix. By induction, write $A^{\prime }={\sum }_i{\beta }_i{P}_i$ as a convex combination. Thenis another convex combination, with nonnegative coefficients summing to one. ThusThis constructive proof of the Birkhoff-von Neumann theorem is Birkhoff decomposition by support matchings.