Spanning graphs and the Axiom of Choice

• Autorzy: Delhommi Ch. , Morillon M.
• Języki publikacji: EN

Abstrakty

EN

We show in set-theory ZF that the axiom of choice is equivalent to the statement every bipartite connected graph has a spanning sub-graph omitting some complete finite bipartite graph Kn;n, and in particular it is equivalent to the fact that every connected graph has a spanning cycle-free graph (possibly non connected).

Słowa kluczowe

EN

axiom of choice; connected graphs; spanning trees

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2006
• Tom: Nr 40
• Strony: 165--180
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Delhommi Ch.

autor

Morillon M.

• ERMIT, Departement de Mathematiques et Informatique, Universite de La Reunion, 15 avenue Rene Cassin - BP 7151 - 97715 Saint-Denis Messag. Cedex 9 FRANCE,

Bibliografia

• [1] J. Barwise, Admissible sets and structures, Springer-Verlag, Berlin, 1975.
• [2] P. Howard and J. Rubin, Consequences of the Axiom of Choice, Mathematical Surveys and Monographs, Vol. 59, AMS, (1998).
• [3] T. Jech, The Axiom of Choice, Studies in Logic, vol. 75, North Holland (1973).
• [4] A. Lévy, Axioms of multiple choice, Fund. Math. 50 (1962), pp. 475-483.
• [5] A.R.D. Mathias, The strength of Mac Lane Set Theory, Annals of Pure and Applied Logic, vol. 110 (2001), pp. 107-234.
• [6] J. Mycielski, Some remarks and problems on the colouring of in finite graphs and the theorem of Kuratowski, Acta Math. Acad. Sci. Hung. 12 (1961), pp. 125-129.
• [7] H. Rubin and J. Rubin, Equivalents of the Axiom of Choice, II, North-Holland, Amsterdam, (1985).