On non-denumerable graphs
Paul L. Erdos, Shizuo Kakutani · Bulletin of the American Mathematical Society · 1943
The present paper consists of two parts.In Part 1 we prove a theorem on the decomposition of a complete graph.This result is then applied in Part 2 to show that the continuum hypothesis is equivalent to the possibility of decomposing the set of all real numbers into a countable number of summands each consisting of rationally independent numbers.PART 1 A graph G is complete if every pair of points of G is connected by one and only one segment.G is called a tree if it does not contain any closed polygon.THEOREM 1.A complete graph of cardinal number m (that is, the cardinal number of the vertices is m) can be split up into a countable number of trees if and only if m ^ fc$i.PROOF.We shall first prove that every complete graph of power t$i can be split up into the countable sum of trees. 1 Let G be a complete graph of cardinal number ML Let {x a }, a n .It is clear that G = U* =3] G n and that for each G n , for every j8 i, there exists one and only one a such that (x a , ^) GG M and ce</3.From this last fact it is clear that G n does not contain any closed polygon.Conversely, let us assume that a complete graph G of cardinal number m is split up into a countable number of trees T n ; G = U" = i!T w .We shall prove that m ^ fc$i.We can again assume that G is represented by a system of segments (x a , Xp), a</3<0, where {x a }, a< , is a well ordered set of cardinal number tn.We shall first decompose each T n into four parts T n ,i, i = l, 2, 3, 4, such that T n ,i and r w , 2 satisfy the condition:(1) Any two consecutive segments of the graphs T n ,i and T n ,2 are of the form: (x a , xp), (x a , x y ), a</3, a 4i satisfy:(2) Any two consecutive segments of the graphs are of the form:(Xp, Xa), (X y , X a ) 9 j8 <«, J <«, JST^Y-