Familie von planaren und nicht-planaren Graph mathematisch beschreiben

Question

ich muss beweisen, dass es keinen Satz φ in FO{E} gibt mit:

G |= φ ⇐⇒ G ist ein planarer (ungerichteter) Graph

Hinweis: Betrachten Sie den folgenden planaren Multi-Graphen2 G und den nicht-planeren Graphen H:

Konstruieren Sie nun zwei Familien (Gn)n∈N und (Hn)n∈N von planaren bzw. nicht-planaren ungerichteten Graphen (keine Multi-Graphen!) und verwenden Sie dann die Methode von Eh- renfeucht und Fraïssé. Es genügt, die Gewinnstrategien der Duplikatorin in den entsprechenden Ehrenfeucht-Fraïssé-Spielen nur zu skizzieren. 

Könnte jemand mir dabei helfen. Mein Problem liegt daran, dass ich nicht genau weiss, wie man eine Familie von Graphen ausdrucken kann.

Danke.

Answer 1

Eine Familie (G_n)_n∈ℕ von Graphen kann zum Beispiel rekursiv ausgedruckt werden:

Sei G=(V,E) ein Graph.

G₁ := G

C_n = (V_Cn,E_Cn) sei ein zu G_n = (V_n,E_n) isomorpher Graph mit V_n∩V_Cn = ∅ für alle n ∈ ℕ.

G_n+1 := (V_n ∪ V_Cn, E_n ∪ E_Cn) für alle n ∈ ℕ.

Ob die so erhaltene Familie geeignet ist, habe ich nicht untersucht. Ich habe schon lange keine Ehrenfeucht-Fraïssé-Spiele mehr gespielt.