Acta Mathematica Academiae Scientiarum Hungaricae 66. (1995)

1995 / 1-2. szám - Nahum, R. - Zafrany, S.: Topological complexity of graphs and their spanning trees

2 R. NAHUM and S. ZAFRANY uncountable then a и-analytic minimal spanning tree for W does not always exist. Finally, we list some open problems. 0. Preliminaries A graph G is a pair of sets (V,E) such that E С [F]2 — {{x,t/} | x,y G G F}. Elements of F are called vertices and elements of E are called edges. We also denote F by V(G), and E by E(G0- A path in G is a finite sequence p = (zo, xi,... , xn) of distinct vertices of G such that {x,-,x;+i} G E(<j) for every i < n. A graph G is connected if for every u, v 6 V(G) there is a path p = z„_i, v) in G. This is an equivalence relation on V(G'), and its equivalence classes are called connectivity components, or components, for short. A cycle in G is a path p = (xo, xi,..., xn) such that n ^ 2 and {xra, Xo} G TJ(G'). A forest is a graph with no cycles. A tree is a connected forest. A graph G' = (V', E') is a subgraph of a graph G = (F, E) if V Q V and E' Q E. We also say that G extends G'. If V = F then G' is a spanning subgraph of G. If, in addition, G' is a tree then G' is a spanning tree of G. By a simple use of Zorn’s Lemma one gets the following theorem. Theorem 0.1. Let F be a forest in a connected graph G. Then F can be extended into a spanning tree of G. Let X be a perfect Polish space, i.e., a perfect separable complete metric space. A set В Q X is called Borel if В belongs to the ст-algebra generated by all the open subsets of A; В is analytic if В is a set, i.e., В is a continuous image of some Borel subset of some perfect Polish space; В is co-analytic if В is a. IlJ set, i.e., X — В is а set. We call В a-analytic if В belongs to the <7-algebra generated by all the analytic subsets of X. Let R and R* be binary relations. We say that R* uniformizes R if R* £ R, R* is a function, and dom(i2) = dom(f?*). The axiom of choice implies that any binary relation can be uniformized by some function, but it does not specify the function. In particular, if R ^ XxX, we would like R* to have a not much greater topological complexity than R. This is true in some cases. For example, The Kondo-Addison Uniformization Theorem asserts that if R is a II [ relation then it can be uniformized by а П \ relation (see Kondo [4] and Addison [1]). Another theorem which we use in this paper is: Theorem 0.2. Let X, Y be two perfect Polish spaces. (i) Every analytic relation R ^ X xY can be uniformized by a a-analytic relation. (ii) There is a Borel relation R Q X xY such that R cannot be uniformized by an analytic relation and dom (R) = X (Indeed, R can be chosen to be Ta). Acta Mathematica Hungarica 66, 1995

Next