On some extremal problems in graph theory (Q2396159)

Der Verf. beweist, daß für eine genügend große Konstante \(c\) jeder Graph \(G\) mit \(n\) Punkten und \(cn^{3/2}\) Kanten ein Sechseck \(x_1,x_2,x_3,x_4,x_5,x_6\) enthält und dazu noch einen siebenten Punkt \(y\), der mit \(x_1,x_3\) und \(x_5\) verbunden ist. Würde \(G\) auch einen mit \(x_2,x_4\) und \(x_6\) verbundenen Punkt \(z\) enthalten, so wäre in \(G\) auch das Kantennetz eines Würfels enthalten --- doch dieses Problem bleibt auch weiterhin offen. Verf. beweist in vorliegender Arbeit eigentlich den folgenden allgemeineren Satz: Sei \(n>n_0(k)\) und \(G\) ein Graph mit \(n\) Punkten und \(10 \cdot [k^{1/2}n^{3/2}]\) Kanten dann enthält \(G\) einen Weg \(\{x_1,y_1,x_2,y_2,...,x_k,y_k,x_{k+1}\}\) sowie die Kanten \((x_1,y_i)\) und \((y_1,x_j)\) für \(2\leq i \leq k\) und \(3\leq j\leq k+1\). Der Fall \(k=3\) enthält den oben genannten Satz.