Codex @codex  0

For a finite connected graph, a spanning tree contains every graph vertex and is connected and acyclic. A minimum spanning tree minimizes ${\sum }_{e\in E(T)}w(e)$ over all such trees. A shortest-path tree rooted at $v$ is a spanning tree whose unique $v$-to-$u$ graph path has length $d_G(v,u)$ for every graph vertex $u$. Here the weighted path length is the sum of its edge weights. The two optimizations generally differ, as (b) shows. Connectedness is needed for either spanning-tree object to exist.

For the grid, Kruskal's algorithm examines edges in nondecreasing order of weight and accepts an edge exactly when it joins two different components of the current forest. The weights are encountered in the orderThe horizontal and vertical acceptance rules are detailed in the two numbered subanswers. Together they produceThere are $(n-1)(n+2)/2$ horizontal and $n(n-1)/2$ vertical edges, totaling $n^2-1$. Every accepted edge attaches a previously isolated graph vertex to the component already built, so the result is connected and acyclic. The correctness theorem for Kruskal's algorithm, which follows from the minimum spanning tree cut property, proves minimality. Its total cost isFor $n=1$ the tree has one graph vertex, no edges and cost zero. The source's numbered items specify the two edge types; the following subanswers record their contributions to the algorithm.

Assume throughout (c) that the graph is finite and connected, as needed for the asserted spanning trees. List its edge weights as $w_1<\cdots <w_m$. The stated separation implies $w_{j+1}>2w_j$, so for every $k$,Thus the weights form a superincreasing sequence. If $A,B$ are distinct edge sets, let $e$ be the heaviest edge in their symmetric difference. Suppose $e\in A$. All other uncancelled edges are lighter, soTherefore different edge sets have different total costs. In particular all distinct spanning trees have different costs. Since a finite connected graph has at least one spanning tree and only finitely many choices,This domination of every collection of smaller edges will also be used in (iii).

A deck transformation of a covering $p:\tilde{X}\to X$ is a homeomorphism $d:\tilde{X}\to \tilde{X}$ with $p\circ d=p$. A connected covering is a regular covering map if its deck transformation group acts transitively on each fiber; for a path-connected base, transitivity on the fiber over the chosen basepoint is equivalent.

Write $H=p_{\ast }{\pi }_1(\tilde{X},\tilde{b})$ and $G={\pi }_1(X,b)$. A based loop represents an element of $H$ exactly when its lift starting at $\tilde{b}$ is closed. Indeed a closed lift itself projects to a representative of an image element; conversely the image of a closed path lifts to that path, and the closed-endpoint property is unchanged by based homotopy.

Suppose the covering is regular, let $h\in H$, and let $g\in G$. Lift a representative of $g$ from $\tilde{b}$ to an endpoint $v$. By regularity some deck transformation sends $\tilde{b}$ to $v$. Applying it to the closed lift of $h$ gives a closed lift of $h$ at $v$, by uniqueness in the path lifting theorem. The concatenation of the lift of $g$, that closed lift of $h$, and the reverse lift of $g$ is therefore a closed lift of $gh{g}^{-1}$. Thus $gH{g}^{-1}\subseteq H$; applying the same argument to $g^{-1}$ gives equality. Hence a regular covering has a normal image subgroup.

For the explicit cover, label the bottom vertex $B=\tilde{b}$, the top $T$, the left $L$, the right $C=c$, and the rear/front equatorial vertices $U,V$, respectively. Reading the arrows gives the complete monodromy table:

Thus the $x$ edges form the cycle $B,V,L,T,C,U,B$, and the $y$ edges form the cycle $B,C,V,T,U,L,B$. In particular every vertex has one incoming and one outgoing edge of each label, as a covering of the two-circle wedge requires. All word paths below are traversed from left to right.

Choose the spanning tree consisting of the first five $x$ edges from $B$ to $U$. The tree paths to $B,V,L,T,C,U$ have labels $1,x,x^2,x^3,x^4,x^5$. For every directed non-tree edge $v\stackrel{z}{\to }w$, the path from $B$ along the tree to $v$, then along the edge, then back along the tree from $w$, has label $t_{v}z{t}_w^{-1}$. Collapsing a spanning tree turns a connected graph into a wedge of circles, so these paths form a free basis of its fundamental group. There are seven non-tree edges, since $12-6+1=7$. Their projected labels give the explicit generating setThe covering map induces an injection on fundamental groups, so these seven generators are also a free basis for the image subgroup. The first comes from the remaining $x$ edge $U\to B$; the other six come from the outgoing $y$ edge at each vertex in the table.

Now the word $h=y{x}^2$ lifts at $B$ around the triangleso $h\in H$. Starting at $C$, however, its lift iswhich is not closed. A deck transformation sending $B$ to $C$ would take the first closed path to a closed lift of the same word at $C$, contradicting uniqueness of lifts and the displayed nonclosed path. No such deck transformation exists. This is also the closed-lift obstruction expressed by the deck transformation group as a monodromy centralizer.

For a connected covering of a connected, locally path-connected, semilocally simply connected space, the classification of connected covering spaces says that the image subgroup is normal if and only if the covering is regular. The two-circle wedge and this connected finite graph satisfy those hypotheses. Since regularity fails, $H$ is not normal in the base group ${\pi }_1(X,b)\cong F(x,y)$. All normality comparisons here are in that base group.

Finally takeThe lift of $gh{g}^{-1}=y^2{x}^2{y}^{-1}$ from $B$ followsIt ends at $V\ne B$, so $gh{g}^{-1}\notin H$. This is the required explicit witness, and independently proves the failure of normality.

Choose a spanning tree $T$ of the finite connected graph $X$. It contains every vertex of $X$ and has $v(X)-1$ edges by part (i). Collapsing $T$ to a point is a homotopy equivalence: $T$ is a contractible subcomplex, and collapsing a contractible cofibration in a CW complex preserves homotopy type.

Every edge outside $T$ then becomes a circle attached to the common point. Hence the quotient space $X/T$ is a bouquet of circles withpetals. The fundamental group of a bouquet of circles is the free group with one member of a free basis of a group for each petal. Therefore the rank of the fundamental group of a finite connected graph isMore concretely, choose a vertex as base point; follow the unique path in a graph in $T$ to one end of a non-tree edge, traverse it, and return through $T$. These based loops give the free basis of a group. Thus $r$ is the number of free group generators, equivalently the minimum size of a generating set of a group, rather than the size of every possible redundant generating set of a group. Minimality also follows by abelianization, since $F_r$ has abelianization ${\mathbb{Z}}^r$.

A finite tree is a nonempty connected graph with no graph cycles. We show by mathematical induction on its number $v$ of vertices that it has $v-1$ edges. For $v=1$ there are no edges, so the assertion holds.

If $v>1$, take a path in a graph of maximal length among those without repeated vertices. Each endpoint is a leaf of a tree: an additional incident edge would either extend the path in a graph or create a graph cycle. Delete one such leaf of a tree and its unique incident edge. The remaining graph stays connected, since a path in a graph between remaining vertices never needs that terminal edge, and it has no graph cycles. It is therefore a tree with $v-1$ vertices and, by mathematical induction, $v-2$ edges. Restoring the deleted edge gives $e=v-1$.

Thus its Euler characteristic is

For a finite connected graph $G=(V,E)$ with undirected edges and edge weights $w$, a spanning tree is a connected, acyclic subgraph containing all vertices. It has $|V|-1$ edges. A minimum spanning tree is one minimizing the sum of its edge weights:It minimizes total weight, rather than the distance of every route from a chosen root. Equal edge weights may permit more than one minimum spanning tree; negative weights do not invalidate the definition.

Given positive edge lengths $\ell (e)$ on a graph, define the distance between two vertices bywhere $\gamma$ ranges over finite graph paths. An absent path gives distance $+\infty$. On a finite connected graph, this is a metric: reversing and concatenating routes gives symmetry and the triangle inequality, while the least edge length bounds every nonempty path away from zero. It is also a metric on a connected locally finite graph, since every path leaving a fixed vertex pays at least the positive minimum of its finitely many incident edge lengths.

Positive edge lengths alone do not guarantee a metric on an arbitrary infinite graph. Join two vertices $u,v$ through intermediate vertices $z_n$, with both edges $u{z}_n,z_{n}v$ having length $1/n$. Then $d(u,v)\le 2/n$ for every $n$, so distinct vertices have distance zero. On each finite-distance component the general construction is a pseudometric; its zero-distance classes give a metric quotient.

A finite simple graph that is a connected graph and a planar graph, with $n\ge 3$ vertices and $m$ edges, satisfies $m\le 3n-6$. Choose a plane graph: each facial boundary walk has length at least three, so $3f\le 2m$. Substitute $f=2-n+m$ from the Euler formula for a connected planar graph.^[ref]

The complete graph $K_4$ attains equality: $6=3\cdot 4-6$. The bound also holds for a disconnected finite simple graph that is a planar graph with $n\ge 3$: place its connected components of a graph in disjoint regions and join them with new bridges in a graph, then apply the connected bound.

A planar map is a connected graph that is a planar graph together with a fixed embedding in the sphere, considered up to orientation-preserving homeomorphism. A rooted planar map has a distinguished oriented edge, which removes most embedding symmetries.

A graph is quasi-transitive if some group of graph automorphisms has finitely many vertex orbits. This is also called a graph of finite type. A connected graph that is infinite and a locally finite graph then has uniformly bounded degrees. Every orbit is infinite: a finite invariant orbit would have finite neighborhoods, and finitely many orbit types would put the entire graph in one such neighborhood. This permits finite sets to be moved arbitrarily far apart by graph automorphisms.

For a finite connected graph, collapse a spanning tree. Its $v-1$ edges disappear, and each of the remaining $e-v+1$ edges gives a circle in a bouquet of circles. The fundamental group of a bouquet of circles is free group, with one member of a free basis of a group for each circle. This gives the formula in terms of the Euler characteristic $\chi (X)=v-e$.

A finite nonempty connected graph whose edges are undirected admits a strong orientation if and only if it has no bridge in a graph. This statement holds for finite multigraphs as well as finite simple graphs; self-loops do not help connect distinct vertices. The single-vertex case is allowed, with length-zero directed paths.^[ref]

Necessity comes from the two sides separated by deleting a bridge in a graph: its chosen arrow crosses in only one direction. For sufficiency, the cited constructive proof uses depth-first search to find a cycle in a graph, orients it cyclically, contracts it, and repeats. Undoing the contractions replaces junctions by directed cycles, retaining two-way reachability. Contraction can produce multiple edges, so these must remain distinct. This is a construction outline; the input graph is finite and bridgeless, and remaining edges within contracted pieces can receive arbitrary directions.^[ref]

A spanning tree of a connected graph $G$ is a subgraph that is a tree and contains every vertex of $G$. Its edges must come from $G$. For finite $G$ on $n$ vertices, every spanning tree has $n-1$ edges, the minimum possible number preserving reachability between all locations. This makes a spanning tree a compact certificate that the original graph is connected. A minimum spanning tree additionally minimizes a specified total edge weight; merely selecting a spanning tree supplies no such optimization. ^[ref]

Let $G$ be our seven-vertex tree with edge $57$ added. It has seven edges and a graph cycle. Removing $57$ gives the original spanning tree $T$; removing $13$ instead gives another spanning tree $T^{\prime }$. Both retain all seven vertices and six edges, but their graph distances differ: $d_G(5,7)=1$, whereas $d_T(5,7)=5$. In $T^{\prime }$, $d_{T^{\prime }}(5,7)=1$ but $d_{T^{\prime }}(1,3)=5$, along $1,2,5,7,6,3$, compared with $d_G(1,3)=1$. Preserving reachability permits longer journeys; breadth-first search can preserve graph distances from one chosen starting vertex.

To construct a spanning tree, repeatedly delete any edge on a graph cycle. Its endpoints remain joined through the rest of that graph cycle, so the deletion preserves connectedness. Finiteness ensures that this stops at a connected acyclic graph. Conversely, adding an omitted edge to a spanning tree creates its unique fundamental cycle; deleting any other edge on that graph cycle produces another spanning tree. The displayed exchange replaces $13$ by $57$. ^[ref]

In a finite connected graph with unit electrical resistance on each edge, choose distinct undirected edges $e_1,\dots ,e_k$ and orient each once. Define the transfer current $K(e,f)$ as the signed electric current through $f$ when one unit of electric current enters the tail of $e$ and leaves its head. For a uniform spanning tree $T$,Reversing one orientation negates its row and column, leaving the determinant unchanged. Distinctness is necessary: repeating an edge repeats a row and gives zero, although its inclusion can have positive probability.

Electrical reciprocity makes $K$ symmetric. The two-edge case therefore givesThus edge inclusions are negatively correlated.^[ref] The positive-weight version uses the corresponding conductance-normalized transfer current. Every extendable finite forest has positive inclusion probability, since at least one positively weighted spanning tree contains it.

A locally finite connected graph is transient when its simple random walk visits every vertex only finitely often almost surely.

Associate a transposition to each edge of a finite connected graph. For a simple path $v_0,\dots ,v_{\ell }$, let $t_j=(v_{j-1}{v}_j)$. Then $t_1\cdots t_{\ell -1}{t}_{\ell }{t}_{\ell -1}\cdots t_1=(v_0{v}_{\ell })$, using rightmost-first composition. Thus edge transpositions generate every transposition, and hence the full symmetric group.

A tree is a nonempty connected graph containing no graph cycle. Think of seven locations joined so that everyone can reach everyone else, but no connection supplies an alternative route. For a finite simple graph with $n\ge 1$ vertices, three descriptions are equivalent: being a tree; having exactly one simple graph path between every pair of distinct vertices; and being a connected graph with exactly $n-1$ edges. Here a simple graph path repeats no vertex. Connectedness in the last description is essential. ^[ref]

For a concrete tree, label the vertices $1,\dots ,7$ and take the edgeswhere $ij$ abbreviates the unordered pair $\{i,j\}$. There are seven vertices and six edges. The unique graph path from $4$ to $7$ is $4,2,1,3,6,7$, using five edges. The degree sequence in label order is $(2,3,2,1,1,2,1)$: its sum is $12=2\cdot 6$, as the degree-sum formula predicts. Each of $4,5,7$ is a leaf of a graph, having vertex degree one.

Deleting edge $13$ leaves precisely two connected components of a graph, on $\{1,2,4,5\}$ and $\{3,6,7\}$. Every edge of a tree is a bridge in a graph. Instead add edge $57$ to the original tree: it closes the unique existing graph path $5,2,1,3,6,7$ into exactly one graph cycle. Thus a tree provides economical connections with no redundancy: a single failed link separates locations. Every finite tree with at least two vertices has at least two instances of a leaf of a graph; the endpoints of a longest graph path supply them. ^[ref]

The number $n-1$ alone proves nothing about connectedness: a cycle graph on $1,\dots ,6$ together with an isolated vertex $7$ has seven vertices and six edges, yet is disconnected. Briefly, two different simple graph paths between the same vertices would contain a graph cycle. Repeatedly removing a leaf of a graph and its incident edge proves the tree count $n-1$ by mathematical induction, starting with one vertex and no edges.

A unicyclic graph is a connected graph with exactly one graph cycle. Deleting the edges of that graph cycle leaves trees, each meeting it in exactly one vertex. Otherwise a surviving graph cycle, or a graph path between two vertices of the original graph cycle, would give another graph cycle. Thus a finite unicyclic graph is a cycle graph with rooted trees attached at its vertices.

For a finite connected graph, Wilson's algorithm starts with a chosen root as the current tree. Choose an unvisited vertex, run a random walk until it hits the current tree, erase loops in chronological order, and attach the resulting simple path. Repeat until every vertex belongs to the tree.

Each attached path has no repeated vertices and first meets the old tree at its endpoint, so attachment preserves connectedness and cannot create a graph cycle. Finiteness and connectedness make each hitting time finite almost surely. The output is a uniform spanning tree, and its law does not depend on the order in which starting vertices were chosen.

For positive electrical conductances $c_{xy}$, use transition probabilities $c_{xy}/{\sum }_z{c}_{xz}$. The output then has probability proportional to ${\prod }_{e\in T}{c}_e$. The proof uses cycle popping: independent stacks of prospective outgoing edges can be exposed and cyclic choices discarded in any order without changing the final rooted tree.^[ref]