Topological complexity of graphs and their spanning trees (Q1804745)

Let \(X\) be a perfect Polish space. Let \(G = (V,E)\) be a simple graph such that \(V \subseteq X\). Let \(\vec E = \{(x,y) \mid \{x,y\} \in E\}\). We call \(G\) analytic if \(\vec E\) is an analytic subset of the perfect Polish space \(X \times X\). Similarly, \(G\) is \(\sigma\)-analytic if \(\vec E\) belongs to the \(\sigma\)-algebra generated by all the analytic subsets of \(X \times X\). Having assigned this topological complexity to \(G\), one may ask questions concerning the topological complexity of objects related to \(G\). In this paper we study spanning trees. The basic question is: Given the topological complexity of \(G\), how simple can a spanning tree of \(G\) be? By Zorn's Lemma, it is easy to show that every forest \(F\) in a connected simple graph \(G\) can be extended into a spanning tree of \(G\), but the proof is not constructive. In Section 1 we show that if \(G\) is analytic, \(F\) is \(\sigma\)-analytic, \(V(F)\) is analytic, and \(F\) has countably many connectivity components, then \(F\) can be extended into a \(\sigma\)- analytic spanning tree of \(G\) (Theorem 1.2). In Section 2 we study weighted graphs. A weighted graph is a triple \(W = (G, {\mathbf w}, \lambda)\) such that \(G = (V,E)\) is a simple graph, \(\lambda\) is an ordinal, and \({\mathbf w} : E \to \lambda\). For every \(\beta < \lambda\), let \(G^\beta\) be the subgraph of \(G\) consisting of all edges \(u \in E\) such that \({\mathbf w} (u) = \beta\). Here we are looking for a spanning tree of \(G\) whose ``total weight'' is as small as possible. This makes a clear sense in case that \(G\) and \(\lambda\) are finite. In the infinite case, \textit{Ron Aharoni} [Discrete Math. 95, No. 1-3, 5-22 (1991; Zbl 0763.05074)] gave the definition: \(T\) is a minimal spanning tree of \(W\) if \(T\) is a spanning tree of \(G\) and if we replace one edge in \(T\) by a lighter edge, then \(T\) stops being a spanning tree. First, we prove a purely combinatorial fact: every connected weighted graph has a minimal spanning tree (Theorem 2.2). Then we prove a topological version of this fact: Let \(W = (G, {\mathbf w}, \lambda) \) be a connected weighted graph where \(G\) is an analytic graph, \(\lambda\) is a countable ordinal, and for every \(\beta \in \lambda\), the graph \(G^\beta\) is analytic and has countably many components. Then \(W\) has a \(\sigma\)-analytic minimal spanning tree (Theorem 2.4). In Section 3 we show that Theorem 2.4 is optimal. First, we show that an analytic minimal spanning tree for \(W\) does not always exist. Second, we show that if \(G^\beta\) has uncountably many components for some \(\beta \in \lambda\) or \(\lambda\) is uncountable then a \(\sigma\)-analytic minimal spanning tree for \(W\) does not always exist. Finally, we list some open problems.