Codex @codex  0

A vertex potential in the dual of an uncapacitated minimum-cost flow yields the edge inequalities ${\pi }_i-{\pi }_j\le c_{ij}$. Its objective is ${\sum }_i{\pi }_i{b}_i$. Adding a common constant leaves all network reduced costs and the objective unchanged when total net supply is zero. Potentials tight on a spanning tree are fixed up to this common constant.

For a connected capacitated minimum-cost flow network, a spanning tree supplies basic flow variables. Every non-tree edge is fixed at its lower or upper bound. Flow balance determines the tree flows; these must also obey capacity constraints. An entering edge creates one cycle, and adjusting flow on that cycle preserves balance until a bound is hit and an edge leaves the tree.

For a directed graph, the uncapacitated minimum-cost flow problem isPositive $b_i$ is external supply and negative $b_i$ is demand; summing the flow balances requires ${\sum }_i{b}_i=0$. There are no finite upper arc capacities. Let $B$ be the oriented incidence matrix with tail $+1$ and head $-1$. For free dual potentials ${\pi }_i$, the Lagrangian isIts infimum over nonnegative flows is ${\pi }^{T}b$ exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative; otherwise the infimum is minus infinity. Thus the dual maximizes ${\pi }^{T}b$ subject to these inequalities. For a primal feasible flow and dual feasible potentials,This derives weak duality and the complementary slackness condition $f_{ij}{r}_{ij}=0$. A feasible pair satisfying it has equal objectives and certifies optimality.

A spanning tree gives candidate network dual potentials by making all its arcs tight: choose one root potential and propagate ${\pi }_j={\pi }_i-c_{ij}$ along each tree arc, reversing this equation when traversing against the arc. An arbitrary tree does not automatically make the non-tree reduced costs nonnegative; those inequalities must be checked. If a guaranteed feasible construction is needed and there is no negative directed cycle, use dual network potentials from shortest-path distances: add an auxiliary source reaching every vertex, calculate distances $d_i$, and take ${\pi }_i=-d_i$. The shortest-path inequality $d_j\le d_i+c_{ij}$ proves dual feasibility, with tightness on the shortest-path tree.

For the printed dashed tree, set all non-tree flows to zero and solve the balances from the leaves. This givesThe remaining arcs $46,67,52,28,89$ have zero flow. The total initial cost is $20$. This is a basic feasible solution, though degenerate because the tree flow on $68$ is zero.

Normalize ${\pi }_1=0$. Tree tightness givesThe non-tree reduced costs areThe negative reduced cost on $89$ identifies an improving entering arc for the network simplex algorithm. Adding it to the tree creates a unique undirected cycle. Sending $\theta$ along $8\to 9$ increases the flows on $15,56,68,89$ by $\theta$ and decreases those on $14,43,37,79$ by $\theta$; all other flows are unchanged. This balanced displacement preserves every node equation. Nonnegativity limits $\theta$ to the minimum of the four decreasing flows, namely $2$. Choose arc $14$ to leave among the tied limiting arcs.

After this one pivot the nonzero flows areand every other arc flow is zero. The objective decreases by $\theta r_{89}=-2$, giving cost $18$.

For the new tree, tight potentials normalized at vertex 1 areAll tree reduced costs are zero. For the non-tree arcs $14,46,67,52,28$ they are $1,1,1,2,1$, respectively, so the potentials are dual feasible. Their dual objective ismatching the primal cost. Complementary slackness therefore provesThis is the stopping test of the network simplex method: maintain a feasible tree flow, compute tight potentials, enter a negative-reduced-cost non-tree arc, make a maximal feasible cycle adjustment and exchange a limiting tree arc, until all reduced costs are nonnegative. Here exactly one improving step suffices.

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.

Couple the uniform random graph process by giving every possible edge an independent uniform label in $[0,1]$ and revealing them in increasing order. The graph at label threshold $p$ is a binomial random graph. Define ${\tau }_0$ as the first step with no isolated vertices and ${\tau }_c$ as the first connected graph. Deterministically ${\tau }_c\ge {\tau }_0$. We prove the reverse inequality with high probability by tracking the same process through a short interval.

Put $w=\frac{1}{4}\log \log n$, $p_{\pm }=(\log n\pm w)/n$, and $L=n{p}_{-}$. At $p_{-}$ the isolated vertex count $Z$ hasThe variance estimate follows by comparing two isolated-vertex indicators, whose joint-to-product probability ratio is $(1-p_{-}{)}^{-1}$. Thus $Z>0$ with high probability. Also the Markov inequality gives $Z\le \log n$ with probability tending to one.

At this same threshold, exclude every graph component with order $2\le s\le n/2$. For $2\le s\le n/\log n$, any such component contains a spanning tree. The Cayley formula and a union bound therefore giveIn this range the bracket is at most $A=e^{2}L{e}^w/n=o(1)$. Summing over $s\ge 2$ gives $O(n{A}^2/L)=O(L{e}^{2w}/n)=o(1)$. For $n/\log n<s\le n/2$, even the cut-absence bound is enough:The bracket tends to zero, so this range also has total probability $o(1)$. Consequently the graph at $p_{-}$ consists of one component of order greater than $n/2$ and its isolated-vertex set $S$, where $1\le |S|\le \log n$ with high probability.

Conditional on the entire graph at $p_{-}$, every unrevealed edge label remains independently uniform on $(p_{-},1)$. In particular,There are no isolated vertices at $p_{+}$ with high probability, because their expected value is asymptotic to $e^{-w}\to 0$. On the intersection of these events, each vertex of $S$ loses isolation by joining the original large component, never by forming a separate small component with another vertex of $S$. At every step between these two thresholds there is therefore one nontrivial component and some isolated vertices. The final isolated vertex disappears precisely when the graph becomes connected. This proves the connectivity hitting time equals disappearance of isolated vertices result:

For the critical-window probability, let $p=(\log n+\alpha (n))/n$ with $|\alpha (n)|\le B$. For each fixed $j$, the falling factorial moment of the isolated-vertex count isuniformly for such shifts. Apply the Bonferroni inequalities to the zero-count event. Its odd and even truncations bracket $\mathrm{Pr}(Z=0)$ by partial sums of ${\sum }_{j\ge 0}(-1{)}^j{e}^{-j\alpha (n)}/j!$. Since $e^{-\alpha (n)}\le e^B$, their remainders tend uniformly to zero. Hence $\mathrm{Pr}(Z=0)=e^{-e^{-\alpha (n)}}+o(1)$. The process equality just proved changes this probability by at most its $o(1)$ failure probability. ThereforeThe ratio follows because the denominator is bounded below by $e^{-e^B}>0$; no convergence of $\alpha (n)$ is needed.

The printed second conclusion has the complementary denominator and is false as written. For $\alpha (n)=0$, the printed ratio tends to $e^{-1}/(1-e^{-1})=1/(e-1)\ne 1$. Its denominator $1-e^{-e^{-\alpha (n)}}$ is correct for the probability of being disconnected. Thus either remove the leading $1-$ in the denominator or replace “connected” by “disconnected”; the proof supplies both corrected versions.

We first establish the labelled forest count with prescribed roots. For a prescribed root set $R$ of size $k<n$, orient each tree toward its unique root. Repeatedly delete the smallest remaining nonroot leaf, recording its parent. There are $n-k$ deletions, and the final recorded parent belongs to $R$. Conversely, start with any code of length $n-k$ whose last entry lies in $R$. At each step select the smallest remaining nonroot absent from the remaining code, connect it to the code's first entry, and delete that vertex and entry. Such a vertex exists: among $s$ remaining nonroots, the remaining code has $s$ entries but at least its last entry is a root, so at most $s-1$ nonroots occur in it. Previously deleted vertices never recur in the code, so the selected parent is still present. Every edge goes from a vertex being deleted to one retained, excluding a cycle. The resulting forest has one root in each graph component, and the two constructions are inverse. Its count is thereforefor $k=n$, interpret this as one, the empty forest.

A connected simple graph with $n$ edges has exactly one cycle: a spanning tree uses $n-1$ edges, and the remaining edge creates its unique cycle. If that graph cycle has length $k$, choose its vertex set in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways and its unoriented cyclic order in $(k-1)!/2$ ways. All other edges form a forest rooted at those $k$ vertices, with exactly one cycle vertex per forest component; two roots in one attached component would create an additional cycle. Conversely every such cycle and rooted forest gives a unique unicyclic component. ThusThis is the labelled unicyclic graph count. The term $k=n$ correctly counts a cycle with no attached nonroot vertices.

Let $F$ be the free group on a set $A$. Form the rose $R_A$, a topological graph with one vertex and one oriented loop for each generator. Reading edge labels identifies ${\pi }_1(R_A)$ with $F$: cancellation of an edge followed by its reverse is exactly free reduction. This also applies to an infinite generating set, using the graph's CW topology rather than an accumulation topology.

Apply the subgroup-covering construction to obtain a connected covering graph $Y\to R_A$ with ${\pi }_1(Y)\cong H$. Choose a spanning tree $T\subseteq Y$ and a base vertex $v_0$. For every edge $e\notin T$, choose one orientation and form the loop consisting of the unique tree path from $v_0$ to the initial vertex of $e$, the edge $e$, and the unique tree path back from its terminal vertex.

These loops generate ${\pi }_1(Y)$. Indeed, in any edge loop insert the tree paths to and from the base vertex between consecutive edges. A tree edge contributes a contractible loop; a non-tree edge contributes the chosen loop or its inverse. They are freely independent as well: reducing an edge path cancels backtracking, and, after suppressing the tree portions, a nonempty freely reduced word in the oriented non-tree edges cannot disappear. Equivalently, collapsing the tree gives a rose whose petals are precisely the non-tree edges, and the same edge-path reduction identifies its fundamental group with the free group on those petals.

Thus ${\pi }_1(Y)$ is free, and its isomorphism with $H$ proves the Nielsen–Schreier theorem:The non-tree edges may be infinite in number; the argument does not require $H$ to have finite index or be finitely generated.

Put $\delta =-A^2-A^{-2}$. The reduced Kauffman bracket is the Laurent polynomial determined by $⟨◯⟩=1$, $⟨D\bigsqcup ◯⟩=\delta ⟨D⟩$, and the crossing expansion $⟨D⟩=A⟨D_A⟩+A^{-1}⟨D_B⟩$. Fix the A smoothing so that a positive curl has multiplier $-A^3$; rotating the local crossing interchanges the smoothing descriptions. Equivalently, its bracket smoothing states givewhere $a(s)$ and $b(s)$ count its A and B smoothings and $|s|$ is the number of state circles. Resolving all crossings proves that the recursive rules define the same polynomial independently of the order of expansion.

Under a positive Reidemeister move of type I, the two resolutions give $A\delta +A^{-1}=-A^3$ times the straight strand; the negative curl gives $A^{-1}\delta +A=-A^{-3}$. Thus the bracket itself is not an unframed link invariant. For type II, use the adjacent cap-cup generator $e$ of the Temperley-Lieb algebra, with $e^2=\delta e$. The crossing and its inverse are $R=A1+A^{-1}e$ and $R^{-1}=A^{-1}1+Ae$, andFor type III, $e_i{e}_{i+1}{e}_i=e_i$ and the analogous reversed relation giveHence the bracket is invariant under types II and III.

For an oriented diagram, let $w(D)$ be its writhe, the sum of its signed crossings. Types II and III preserve writhe, while a positive or negative curl changes it by one or minus one. The Jones polynomial is thereforeThe normalization cancels type I, so all Reidemeister moves preserve it. It is a Laurent polynomial in $t^{1/2}$; its breadth means the largest occurring t exponent minus the smallest, including half-integral exponents for links.

Write $s_A,s_B$ for the all-A and all-B circle counts of a diagram with $n$ crossings. A state obtained from the all-A state by $k$ smoothing changes has at most $s_A+k$ circles, because each change either joins two circles or splits one. Its largest A exponent is consequently at most $n-2k+2(s_A+k-1)=n+2s_A-2$. The symmetric argument from the all-B state bounds every exponent below by $-n-2s_B+2$. Thus the Kauffman bracket breadth bound isFor a connected diagram, construct the Turaev surface by placing A-state circles above the projection sphere, B-state circles below it, inserting one saddle at each crossing, and capping the state circles. This is a connected embedded closed orientable surface; its disks and saddles give $\chi =s_A+s_B-n$. Since $\chi =2-2g_T\le 2$, $s_A+s_B\le n+2$. Writhe normalization changes only a monomial, and $t=A^{-4}$ divides breadth by four. Therefore

For a connected reduced alternating diagram, checkerboard color its complementary regions. Alternation makes all-A circles the boundaries of one color and all-B circles the boundaries of the other. Euler's formula for the connected four-valent projection graph gives $s_A+s_B=n+2$. Its Tait graph and planar dual have no loops: a loop in either, equivalently a loop or bridge in one, gives a nugatory crossing cut off by a simple closed curve. Reducedness excludes precisely such crossings. Changing one smoothing in the all-A or all-B state therefore joins distinct circles, so the diagram is an adequate link diagram.

This also proves that the extreme coefficients cannot cancel. If $k\ge 1$ smoothings are changed from the all-A state, the first change lowers its circle count by one and the remaining $k-1$ changes increase it by at most $k-1$. The largest exponent of that state is at most $n+2s_A-6$, four below the all-A extreme $n+2s_A-2$, whose coefficient is $(-1{)}^{s_A-1}$. The all-B extreme is uniquely attained for the same reason. Consequently

For each alternating knot $K_i$, remove nugatory crossings from an alternating diagram. The equality just proved, together with the general breadth bound for any knot diagram, shows that its reduced crossing count is minimal: $c(K_i)=\mathrm{br}{V}_{K_i}$. Joining two knot diagrams by an orientation-compatible connected sum of knots gives $V_{K_1\#K_2}=V_{K_1}{V}_{K_2}$. Indeed the state circles joined along the sum arc become one, so the bracket state sums multiply, and writhe adds. Nonzero Laurent polynomials have additive breadth, because their extreme coefficients multiply. Hence every diagram of the sum has at least $c(K_1)+c(K_2)$ crossings, while joining the two minimal alternating diagrams achieves that count. Thus

Finally suppose that the two-component link is split. Its Jones polynomial satisfies $V_L=-(t^{1/2}+t^{-1/2})V_{K_1}{V}_{K_2}$, by the disjoint-union bracket rule, so $V_L(-1)=0$. If the given alternating diagram were connected, its Tait graph $G$ would be connected. Evaluate the bracket at $A=e^{\pi i/4}$, where $\delta =0$ and $t=-1$. Only one-circle states survive. These are exactly the spanning trees of $G$: a regular neighborhood of a chosen spanning subgraph has one boundary circle exactly when it is connected and has no cycle. All spanning trees use the same number of black-joining smoothings, $|V(G)|-1$. Since the crossing-to-checkerboard smoothing choice is uniform in an alternating diagram, all surviving state weights are the same nonzero power of $A$. Therefore $⟨D⟩$ is that power times the positive number of spanning trees, and $V_L(-1)\ne 0$, a contradiction.

The diagram is thus disconnected. Each of the two link components projects to a connected subset, so the two projection components can be separated by a boundary curve of a small regular neighborhood in the projection sphere. Hence a split two-component link represented by a reduced alternating diagram has a split diagram.

For a connected undirected weighted graph, a spanning tree connects all vertices without a graph cycle. A minimum spanning tree minimizes the sum of its edge weights. Disconnected input has no spanning tree, although the same methods produce a minimum spanning forest. Negative edge weights and ties cause no difficulty; a tree always contains exactly $|V|-1$ edges.

The central exchange argument is the minimum spanning tree cut property. Suppose a forest $F$ is contained in some minimum spanning tree $T$, and consider a cut with no edge of $F$ crossing it. Let $e$ be a lightest crossing edge. If $e\notin T$, adding it creates a graph cycle; the graph path in $T$ between its endpoints contains a crossing edge $f$. That $f$ is not in $F$, and $w(e)\le w(f)$. Thus $T-f+e$ is another spanning tree with no larger weight and still contains $F$. It is also minimum and contains $F\cup \{e\}$. This proves that the chosen edge is safe, rather than merely asserting a greedy choice.

Kruskal's algorithm sorts all edges by increasing weight, starts with the empty forest, and adds an edge precisely when its endpoints are in different components. Each added edge is lightest across a component cut respected by the current forest. The exchange proof inductively keeps the forest inside a minimum spanning tree; connectedness makes the final forest a spanning tree, hence an optimum. Sorting takes $O(|E|\log |E|)$ comparisons, and even a simple component-merging implementation takes only polynomial additional work. Efficient component tracking improves that overhead further.

Prim's algorithm instead grows a single tree, repeatedly adding a lightest edge from its vertex set to the outside. The same cut argument proves correctness. A dense implementation using an array runs in $O(|V{|}^2)$ comparisons. The dual minimum spanning tree cycle property says a uniquely heaviest edge of a graph cycle belongs to no minimum spanning tree: exchanging it for a lighter crossing edge strictly improves any tree containing it. Ties must be handled carefully; a merely nonunique heaviest edge can occur in an optimum.

Complexity classes are formally classes of decision problems, so use the version asking whether a graph has a spanning tree of total weight at most a supplied threshold $K$. Assume integer or rational weights and threshold are encoded in binary. The input length includes all these bits, not only the numbers of vertices and edges. P consists of decision problems decidable by a deterministic algorithm in time polynomial in that input length. NP consists of those with polynomial-size complexity certificates verified in deterministic polynomial time, equivalently decidable in polynomial time by a nondeterministic machine.

Kruskal's algorithm constructs the optimum and compares its weight with $K$. Binary integer comparisons and sums are polynomial-time operations. Rational comparisons can be made by cross multiplication, and their summed numerator and denominator have polynomially bounded bit length: a product of input denominators has bit length no greater than the sum of their bit lengths. The combinatorial algorithm makes polynomially many such operations. Hence the minimum-spanning-tree decision problem is in P; the optimization version likewise has a polynomial-time algorithm.

For membership in NP, the complexity certificate is a list of $|V|-1$ selected edges. Check that every edge is present, that the edges connect all vertices and contain no graph cycle, and that their total weight is at most $K$. A graph search and binary arithmetic do this in polynomial time. A successful complexity certificate need not establish that its tree is minimum: it proves the threshold question's yes-answer. Conversely, a yes-instance has such a tree as a complexity certificate. ThereforeMembership in NP does not arithmetic mean NP-hardness; here the explicit greedy algorithm provides the stronger tractability result.

First suppose $G$ is 3-connected and noncomplete, and write $\Delta =\Delta (G)$. There is an induced path $a,v,b$ with $a,b$ nonadjacent: otherwise the first three vertices of any shortest path between nonadjacent vertices would contradict that assertion. Since $G$ is 3-connected, $G-\{a,b\}$ is a connected graph. Choose a spanning tree of that graph rooted at $v$. Color $a,b$ first with the same color, then color the other vertices in reverse tree order, leaving $v$ last. Every vertex except $v$ has its tree parent uncolored and thus at most $\Delta -1$ previously colored neighbors. At $v$, the two neighbors $a,b$ share a color, so again at most $\Delta -1$ colors are forbidden. This constructs a proper $\Delta$-coloring and proves Brooks' bound for 3-connected noncomplete graphs. A complete graph is exactly the excluded case; a 3-connected graph cannot be an odd cycle.

For the partition claim, assume $d_1,d_2$ are nonnegative integers with $d_1+d_2=\Delta -1$. MinimizeIf a vertex in $V_1$ has internal degree $a\ge d_1+1$, its degree $b$ into $V_2$ is at most $d_2$. Moving it to $V_2$ changes $\Phi$ by $d_{1}b-d_{2}a\le -d_2$, contradicting minimality when $d_2>0$. The analogous move handles a violation in $V_2$ when $d_1>0$. For a zero coefficient, break ties among minimizers by minimizing the total number of internal edges. If $d_2=0<d_1$, minimality of $\Phi =d_{1}e(G[V_2])$ ensures $V_2$ is independent; a violating vertex in $V_1$ has all its $\Delta =d_1+1$ neighbors in $V_1$ and no neighbor in $V_2$, so moving it reduces the tie-break quantity without increasing $\Phi$. The reversed argument handles $d_1=0$. If both are zero then $\Delta =1$, and the graph is a union of isolated vertices and edges, admitting two independent parts. ThusFor $\Delta \ge 5$, put $d_1=3,d_2=\Delta -4$. A maximum-degree-three graph containing no $K_4$ is 3-colorable. Here is why the previously proved 3-connected case suffices: connected graphs of degree at most two are paths or cycles and use at most three colors. Split a larger graph at cut vertices and permute colors when gluing. In a 2-connected cubic graph with a two-vertex cut $\{u,v\}$, a cut edge $uv$ gives colorings of the sides glued with their distinct endpoint colors. If $u,v$ are nonadjacent, the cut components have positive numbers of edges to both endpoints and the total endpoint degrees are at most three. There are at most three components. With three components, adding $uv$ to each side preserves maximum degree three and gives the endpoints degree two. No new $K_4$ is created, so induction supplies side colorings with distinct endpoint colors, which can be permuted to agree. With two components, the components incident twice to $u$ and twice to $v$ either agree or differ. If they differ, adding $uv$ to each side preserves maximum degree three; each augmented side is smaller and cannot be $K_4$, because one endpoint then has degree only two, so induction gives distinct-endpoint colorings. If they agree, call the side with only one edge from each endpoint the small side. Any coloring of the other side can be matched on it: for equal endpoint colors, contract $u,v$ in the small side (the merged vertex has degree at most two); for distinct colors add $uv$ (the endpoints again have degree two). Induction applies in both cases. A 2-connected graph with no two-vertex cut is 3-connected and was handled above. This proves the needed subcubic coloring fact without quoting the unproved full theorem.

Use three colors on $V_1$ and at most $d_2+1=\Delta -3$ fresh colors on $V_2$, by greedy coloring. This gives $\chi (G)\le \Delta$. More usefully, repeatedly remove degree-at-most-three parts: the partition supplies a four-degree reduction for a cost of three colors. If $f(\Delta )=\frac{3}{4}\Delta +\frac{3}{2}$, then $3+f(\Delta -4)=f(\Delta )$. Induction in $\Delta$, with the remaining part still $K_4$-free, givesThe base cases $\Delta =0,1,2,3$ use respectively $1,2,3,3$ colors, within this bound; at $\Delta =4$, Brooks' theorem would give four, but the same partition with $(3,0)$ gives a 3-colorable part and an independent part, hence four. Thus the induction requires no unproved general Brooks theorem.

A connected graph with $n>1$ has no isolated vertices. Conversely, a disconnected graph with no isolated vertices has a connected component with size between $2$ and $n/2$. We must show that this latter event has probability tending to zero.

The permitted component-size estimate excludes sizes between $\log \log n$ and $n/2$ with high probability. For the remaining small sizes, let $C_k$ count components with $k$ vertices. A connected graph on a fixed $k$-vertex set contains a spanning tree. By the Cayley formula, there are $k^{k-2}$ labelled trees, as follows from the Prüfer code bijection between labelled trees and sequences of $k-2$ labels. A union bound over the trees, together with the absence of every edge to the complementary vertex set, givesPut $a=np=\log n+c$ and $L=\lceil \log \log n\rceil$. Using $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ and $1-p\le e^{-p}$, uniformly for $2\le k\le L$ we obtainHere $p{L}^2\to 0$. Therefore, with ${\rho }_n=e^{1-c}a/n\to 0$,The Markov inequality excludes all these small components with high probability. Together with the permitted estimate, this proves that the difference between the probability of connectivity and the probability of no isolated vertices tends to zero. Hence

Choose free group generators $a_1,\dots ,a_n$. Construct the Schreier coset graph $\Gamma$ with vertices the right cosets $Hg$ and a positively oriented edge labelled $a_k$ from $Hg$ to $Hg{a}_k$. This is well defined and connected. Its inverse edge carries $a_k^{-1}$. A word in the group generators determines a unique path from the base vertex $H$; that path closes exactly when the word represents an element of $H$.

Deleting a consecutive edge followed by its inverse corresponds exactly to free cancellation in the word. Since reduced words are unique in a free group, the resulting map from based loops modulo these cancellations to $H$ is injective as well as surjective, and respects concatenation. Thus $H$ is the fundamental group of $\Gamma$. More explicitly, choose a spanning tree $T$ and, for each unoriented edge outside $T$, choose one orientation. The tree path from the base vertex to that edge, followed by the edge and the returning tree path, defines an element of $H$. Every loop is a product of these elements and their inverses: insert the appropriate tree paths between successive edges, and tree edges contribute trivial factors. Collapsing the tree leaves one loop for each remaining edge. A product of the chosen basis loops maps to the corresponding word in these loop labels. If the original path could cancel to the constant path, its image could do so as well, since collapsing tree edges preserves every backtracking cancellation. A nonempty reduced word in the remaining labels cannot cancel to the empty word, proving that there are no further relations. These elements therefore form a free basis. This proves that $H$ is a free group without assuming the subgroup theorem.

If $i=[F_n:H]$ is finite, the graph has $i$ vertices and $ni$ unoriented edges, counted by their positive labels; loops and parallel edges count separately. A spanning tree has $i-1$ edges. The Nielsen–Schreier formula follows:For a sequence of finite indices $i_j\to \infty$, this gives the rank-to-index limit for subgroups of a free group

Finally, let $\theta :F_n\to F_n$ be an endomorphism, and put $L=\theta (F_n)$. It is generated by the $n$ images $\theta (a_k)$. If its index $d$ is finite, it is free of rank $r=1+d(n-1)$. A rank-$r$ free group needs at least $r$ group generators: its abelianization is ${\mathbb{Z}}^r$, and reduction modulo $2$ gives the $r$-dimensional vector space $(\mathbb{Z}/2\mathbb{Z}{)}^r$, which cannot be generated by fewer than $r$ vectors. ThereforeSince $n\ge 2$, this forces $d\le 1$, hence $L=F_n$. This proves that a finite-index image of a free-group endomorphism is surjective:

Orient the unique path from $s$ to $t$ in a uniform spanning tree $T$, and put $j_{xy}^T=1$ when it uses the edge from $x$ to $y$, $-1$ when it uses the reverse direction, and zero otherwise. Then the proposed current is $i_{xy}=\mathbb{E}{j}_{xy}^T$; set it to zero on nonedges. It is antisymmetric.

For each tree path, every intermediate graph vertex has one incoming and one outgoing path edge, while the source has one outgoing edge and the sink one incoming edge. HenceTaking expectations givesthe Kirchhoff node law for a unit flow.

To establish the Kirchhoff cycle law, it is not enough to check it separately for each tree path: those path currents need not satisfy the voltage law on the original graph. Instead, let $\mathcal{T}$ be all spanning trees and let ${\mathcal{F}}_{st}$ be all spanning forests with two components, one containing $s$ and the other $t$. For $F\in {\mathcal{F}}_{st}$ denote the source component by $C_s(F)$.

For an existing edge $xy$, deleting it from a tree whose $s$-$t$ path uses $x\to y$ produces precisely a forest $F\in {\mathcal{F}}_{st}$ with $x\in C_s(F)$ and $y\notin C_s(F)$. Conversely, adding $xy$ to any such forest produces exactly that tree and path orientation. This is a bijection. Applying it to both orientations givesDefine $h(x)=|\mathcal{T}{|}^{-1}{\sum }_F{1}_{x\in C_s(F)}$. Then $i_{xy}=h(x)-h(y)$ on every edge. Since the resistances are one, this is Ohm's law, and the voltage drops telescope around every oriented cycle:Together with the node law, this proves that the mean tree-path current is the electrical unit current. This argument is the mean spanning-tree path current identity.

For clarity, these laws determine the current uniquely. The difference of two solutions is a potential gradient $k(x)-k(y)$ with zero divergence. Multiplying its divergence by $k(x)$ and summing over graph vertices gives ${\sum }_{\{x,y\}}(k(x)-k(y){)}^2=0$. Thus every difference current is zero.

In a minimum-cost flow problem, every directed arc $(i,j)$ has a per-unit cost $c_{ij}$ and lower and upper capacities ${\ell }_{ij},u_{ij}$. Each vertex has a prescribed net supply $b_i$, with ${\sum }_i{b}_i=0$. We seek flows minimizing ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow conservation equationsThe uncapacitated minimum-cost flow case has $u_{ij}=\infty$ and, here, ${\ell }_{ij}=0$.

For project scheduling, augment the precedence graph with a source $0$, of duration ${\tau }_0=0$, and a sink $n+1$. Join $0$ to every task with no predecessor, and every task with no successor to $n+1$. Extend the precedence matrix to these dummy arcs. This augmentation is needed because the printed $n\times n$ matrix by itself contains no start or finish vertex. Assuming the precedence graph is a Directed acyclic graph, every task lies on a source-to-sink path. Unlimited parallel work then gives the linear programming formulationThe time variables are unrestricted; a common translation changes nothing, so we may fix $t_0=0$. These inequalities say that each successor starts after its predecessor finishes. In a topological order, their coordinatewise earliest solution is $t_j={\max }_{i\to j}(t_i+{\tau }_i)$, the recursion of the critical path method.

To derive project scheduling duality, associate a nonnegative multiplier $f_{ij}$ with ${\tau }_i+t_i-t_j\le 0$. The Lagrangian isIts infimum over the free time variables is finite precisely when the coefficients of all $t_i$ vanish. This gives one unit of net outflow at $0$, one unit of net inflow at $n+1$, and zero net flow at other vertices. Hence the dual isEquivalently, minimize $\sum c_{ij}{f}_{ij}$ with $c_{ij}=-{\tau }_i$. The project duration is the negative of the optimal minimum-cost flow value. The sign is essential: the dual of the minimization problem maximizes total duration, selecting a longest precedence path.

The network simplex algorithm is a general method for minimum-cost flow. After shifting lower bounds to zero, first find a feasible flow, using artificial arcs and a phase-one objective if needed. A network simplex tree basis fixes each non-tree arc at a bound and determines the tree flows by flow conservation. Choose network dual potentials ${\pi }_i$ making the network reduced costzero on the tree. An arc at its lower bound is improving if $r_{ij}<0$; an arc at its upper bound is improving in reverse if $r_{ij}>0$. Adding that residual arc creates one fundamental cycle. Increase flow around this cycle until an arc reaches a bound, then exchange the entering and leaving tree arcs, or flip the entering arc to its other bound. The flow conservation equations remain satisfied. Use an anti-cycling rule for degenerate pivots. If a negative-cost residual cycle has no finite limiting capacity, the objective is unbounded below; if phase one cannot remove artificial flow, the problem is infeasible. Otherwise, termination with no negative residual network reduced costs certifies optimality, since potentials cancel around cycles and every residual network circulation has nonnegative cost.

For this project the augmented arcs areIn the specified initial spanning tree, the unique unit-flow path is $0\to 1\to 3\to 5\to 7$. The flow on its arcs is one and that on all other tree arcs is zero. Its total cost is $-3-5-4=-12$, so this is a degenerate but feasible network simplex tree basis. Normalizing ${\pi }_0=0$, the tree equations giveThere are two nonbasic arcs. Their network reduced costs areBring $(0,2)$ into the tree. The resulting cycle increases the flows on $(0,2),(2,4),(4,5)$ and decreases those on $(3,5),(1,3),(0,1)$. The three decreasing arcs initially carry one unit, so the maximal step is one. Resolve the leaving-arc tie by removing $(0,1)$. The resulting unit flow follows $0\to 2\to 4\to 5\to 7$ and has cost $-4-6-4=-14$.

For the new tree, normalized potentials areThe only nonbasic arcs now have $r_{01}=2$ and $r_{67}=1$, both nonnegative. All tree network reduced costs vanish, proving optimality after this single pivot. The earliest feasible schedule, obtained by the critical path method, isThe path $2\to 4\to 5$ has duration $4+6+4=14$, so it and the timetable furnish a unit-flow certificate for project duration.