A convex characterization of the graphs of the dodecahedron and icosahedron (Q794675)

Sei \(\Gamma\) ein ungerichteter zusammenhängender Graph. Ein Pfad minimaler Länge zwischen zwei Ecken heißt geodätisch. Ein induzierter Teilgraph heißt konvex, wenn er zu zwei seiner Punkte stets auch jeden geodätischen Pfad aus \(\Gamma\) enthält. Die Punkte, die Kanten sowie \(\Gamma\) selbst sind triviale Beispiele für konvexe induzierte Teilgraphen von \(\Gamma\). Diese heißen uneigentlich, die übrigen eigentlich. Die Autorin hat in ''A convexity problem in 3- polytopal graphs'' (eingereicht bei Arch. Math.) untersucht, für welche Polyeder der Ecken-Kanten-Graph \(\Gamma\) (P) die Eigenschaft hat, daß die Flächen konvexe Teilgraphen liefern, und daß man so alle eigentlichen konvexen Teilgraphen erhält. Von den fünf platonischen Körpern haben das Dodekaeder D und das Ikosaeder I nicht diese Eigenschaft. Zu einem Polyeder P sei C(P) die Menge der Isomorphieklassen seiner konvexen induzierten Teilgraphen. Die Autorin listet C(D) und C(I) auf (hierbei ist \(D_ 6\) falsch) und zeigt sodann: Sei P ein Polyeder, für den der Ecken-Kanten-Graph einer Fläche von P stets konvex in \(\Gamma\) (P) ist. Dann gilt: Ist \(C(P)=C(D)\), so ist \(\Gamma\) (P) isomorph zu \(\Gamma\) (D); ist \(C(P)=C(I)\), so ist \(\Gamma\) (P) isomorph zu \(\Gamma\) (I).