Acta Mathematica Academiae Scientiarum Hungaricae 66. (1995)

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

TOPOLOGICAL COMPLEXITY OF GRAPHS 3 For a proof of this theorem and for more extensive and detailed discussion of this subject see Kuratowski [5] and Moschovakis [8]. 1. Spanning trees in analytic graphs Let X be a perfect Polish space. Every graph G = (У, E) in this paper is such that V ^ X. Let Ё = { (x, y) | {x, y} £ E } • We call G Borel, analytic, or (7-analytic if E is a Borel, analytic, or а-analytic subset of the perfect Polish space XxX, respectively. Note that if G = {V,E) is an analytic connected graph then V = { x \ Зу : (x,y) £ Ё} is also an analytic subset of X. Lemma 1.1. Let G be an analytic connected graph, and let To be a o­­analytic tree in G such that V(To) is analytic. Then T0 can be extended into a о-analytic spanning tree T of G. Proof. For every n £ N, define by induction two analytic sets Vn ^ X and Rn 2 X xX. Let Vo = V(Tb). For every n £ N, let kn+i — Vn Ujx (3y)[?/ £ Vn A {x,y} £ E(G)] j, Rn = {(x,y) I {x,y} £ E(G), x £ Vn+1, у £ Vn}. By Theorem 0.2(i), each Rn can be uniformized by a cr-analytic relation R*n Q Rn. For every n, define a ст-analytic relation En: En = { (x,y) I (x,y) £ Ä* Л x ^ Vn} . Let T be the subgraph of G whose edges are: E(T) = E(T0) U ( |J { {x, у} I (x, y)E En} KnE N Then T is а-analytic and extends To. It is left to show that T is a spanning tree of G. 1. T has no cycles: Suppose that (xo, x\,..., Xk) is a cycle in T. Since To is a tree, one of the edges in the cycle does not belong to E(To). Therefore, without loss of generality, we may assume that (xo,xjt) £ Eno for some no £ £ N. Hence, x0 £ Vno+1 - Vno and x*, £ Vno. This implies that (x0, xi) ^ Eno (since T*0 is a function), (xo, xj) ^ En for every n ф no (since xo £ V„04.i — - Vno), and {x0,xi} ^ E(T0) (since x0 0 Vno 2 V0 = V(T0)). Hence, it must be that (xi,xq) £ Eni, for some n\ £ N. Then n\ > no, since n\ ^ щ Acta Mathematica Hungarica 66, 1995

Next