Spanning tree

[2] The Internet and many other telecommunications networks have transmission links that connect nodes together in a mesh topology that includes some loops.

By deleting just one edge of the spanning tree, the vertices are partitioned into two disjoint sets.

The fundamental cutset is defined as the set of edges that must be removed from the graph G to accomplish the same partition.

However, deleting the row and column for an arbitrarily chosen vertex leads to a smaller matrix whose determinant is exactly t(G).

If G is a graph or multigraph and e is an arbitrary edge of G, then the number t(G) of spanning trees of G satisfies the deletion-contraction recurrence t(G) = t(G − e) + t(G/e), where G − e is the multigraph obtained by deleting e and G/e is the contraction of G by e.[15] The term t(G − e) in this formula counts the spanning trees of G that do not use edge e, and the term t(G/e) counts the spanning trees of G that use e. In this formula, if the given graph G is a multigraph, or if a contraction causes two vertices to be connected to each other by multiple edges, then the redundant edges should not be removed, as that would lead to the wrong total.

[19] Spanning trees are important in parallel and distributed computing, as a way of maintaining communications between a set of processors; see for instance the Spanning Tree Protocol used by OSI link layer devices or the Shout (protocol) for distributed computing.

[20] Instead, researchers have devised several more specialized algorithms for finding spanning trees in these models of computation.

[22][23] Optimal spanning tree problems have also been studied for finite sets of points in a geometric space such as the Euclidean plane.

The quality of the tree is measured in the same way as in a graph, using the Euclidean distance between pairs of points as the weight for each edge.

However, it is not necessary to construct this graph in order to solve the optimization problem; the Euclidean minimum spanning tree problem, for instance, can be solved more efficiently in O(n log n) time by constructing the Delaunay triangulation and then applying a linear time planar graph minimum spanning tree algorithm to the resulting triangulation.

However, for infinite connected graphs, the existence of spanning trees is equivalent to the axiom of choice.

Zorn's lemma, one of many equivalent statements to the axiom of choice, requires that a partial order in which all chains are upper bounded have a maximal element; in the partial order on the trees of the graph, this maximal element must be a spanning tree.

Therefore, if Zorn's lemma is assumed, every infinite connected graph has a spanning tree.

Therefore, if every infinite connected graph has a spanning tree, then the axiom of choice is true.