Kuratowskis Satz fuer unendliche Graphen?

Axel Boldt

unread,

Nov 12, 2003, 6:51:33 PM11/12/03

to

Hallo,

ist Kuratowskis Satz ueber die verbotenen Minoren planarer Graphen auch
fuer abzaehlbar unendliche Graphen richtig?

Axel

Oswald Jaskolla

unread,

Nov 12, 2003, 9:42:35 PM11/12/03

to

Axel Boldt wrote:
> ist Kuratowskis Satz ueber die verbotenen Minoren planarer Graphen auch
> fuer abzaehlbar unendliche Graphen richtig?

Die Existenz eines dieser Minoren verhindert offensichtlich Planaritaet.

Fuer die andere Implikation tippe ich mal dass ein abzaehlbarer Graph planar
ist genau dann wenn jeder endliche Teilgraph planar ist.

Gruesse,
Oswald
--
_/_/ _/ | Oswald Jaskolla <osw...@jaskolla.net>
_/ _/ _/ | Home: http://www.jaskolla.net/oswald/
_/ _/ _/ _/ | Work: http://www.rwth-aachen.de/iww/
_/_/ _/ _/_/ _/ | Fun : http://www.ptsv-schach.de/

Axel Boldt

unread,

Nov 13, 2003, 1:51:29 PM11/13/03

to

Oswald Jaskolla wrote:

> tippe ich mal dass ein abzaehlbarer Graph planar
> ist genau dann wenn jeder endliche Teilgraph planar ist.

Das ist die Frage, aber ob's stimmt?

Axel

Oswald Jaskolla

unread,

Nov 14, 2003, 8:29:12 AM11/14/03

to

Mittlerweile glaube ich es stimmt nicht. Nimmt man einen in beiden
Dimensionen beidseitig unendlichen Gittergraphen G1, etwa so:
. . . .
. . . .
. . . .
| | | |
...-*---*---*---*-...
| | | |
...-*---*---*---*-...
| | | |
...-*---*---*---*-...
| | | |
. . . .
. . . .
. . . .
und eine disjunkte Kopie G2 davon, verbindet diese durch eine Kante, so
glaube ich, das der resultierende Graph nicht planar ist. K5 und K3,3 kann
ich in dem resultierenden nicht sehen.

An mein GT-Buch komme ich im Moment leider nicht ran und der Beweis den ich
im Internet gefunden haben benutzt Induktion nach der Anzahl der Ecken.

Oswald Jaskolla

unread,

Nov 15, 2003, 6:30:36 AM11/15/03

to

"Axel Boldt" <axel...@yahoo.com> schrieb

Je mehr ich versuche ein Gegenbeispiel zu konstruieren, desto fester bin ich
davon ueberzeugt. Meine letzte Konstruktion sah so aus:

Zwei disjunkte Kopien eines Gittergraphen (V,E) mit V=ZxZ und
E = {(a,a+1);(a,a-1);(a,a-1);(a+1,a) | a in Z}
verbunden durch eine Kante zwischen den beiden Nullpunkten.

Der ist aber planar. Leider komme ich im Moment nicht an mein GT-Buch ran,
und der Beweis den ich im Internet gefunden habe benutzt Induktion.

Gruesse,
Oswald
--
_/_/ _/ | Oswald Jaskolla <osw...@jaskolla.net>
_/ _/ _/ | Home: http://www.jaskolla.net/oswald

_/ _/ _/ _/ | Work: http://www.iww.rwth-aachen.de

Thomas Mautsch

unread,

Nov 18, 2003, 11:49:38 AM11/18/03

to

In <bp52op$25g$1...@nets3.rz.RWTH-Aachen.DE> schrieb Oswald Jaskolla:

> "Axel Boldt" <axel...@yahoo.com> schrieb
>> Oswald Jaskolla wrote:
>> > tippe ich mal dass ein abzaehlbarer Graph planar
>> > ist genau dann wenn jeder endliche Teilgraph planar ist.
>>
>> Das ist die Frage, aber ob's stimmt?

Stimmt nicht.
Wenn man aus einem K_5 oder K_{3,3} eine Ecke oder den "Mittelpunkt" einer
Kante entfernt und die mit diesem Punkt verbundenen Kanten (bzw. "Halbkanten")
durch eine unendliche Kette
*----*----*----*----*----*----*--...
ersetzt, sind die entstehenden abzaehlbaren Graphen nicht planar.

Nach einem Satz von Halin (``Zur h"aufungspunktfreien Darstellung
abz"ahlbarer Graphen in der Ebene'', Arch. Math., 1966)
hat jeder *zusammenh"angende* planare Graph eine Einbettung in die Ebene
*ohne H"aufungspunkte* genau dann, wenn er keinen Verfeinerung von
K_5, K_{3,3} oder der oben angegebenen Graphen enth"alt.

Falls man mehr (aber endlich viele) H"aufungspunkte im Graphen zul"asst,
wird die Liste der Ausnahmegraphen gr"o/3er, siehe auch:
http://www.math.uwaterloo.ca/~brichter/pubs/halink.ps

Hoffe, jetzt nichts Falsches geschrieben zu haben.
Thomas