bezeichnet mit G^p, besteht aus der Eckenmenge E(G) eines GraphenG, mit der Vorschrift, daß zwei Ecken u und v genau dann adjazent in G^p sind, wenn für den Abstand d_G(u, v) ≤ p gilt, wobei p eine natürliche Zahl bedeutet. Man spricht dann genauer auch von der p-ten Potenz des Graphen G.

Im Jahre 1974 bemerkte D.P. Sumner, daß G² ein perfektes Matching hat, falls G ein gerader zusammenhängender Graph ist. Entsteht der BaumT aus dem vollständigen bipartiten Graphen K_1,3 durch zweifaches unterteilen jeder Kante, so überzeugt man sich leicht davon, daß in T² kein Hamiltonscher Kreis existiert. Im Jahre 1960 zeigte M. Sekanina, daß sich die Situation ändert, wenn man anstelle von T² die dritte Potenz eines Graphen betrachtet:

Ist G ein zusammenhängender Graph mit mindestens 3 Ecken, so ist G³Hamilton-zusammenhängend.

Mittels eines schwierigen Beweises konnte H. Fleischner 1974 dann folgende Vermutung von C.St.J.A. Nash-Williams und M.D. Plummer bestätigen.

Ist G ein Graph ohne Artikulation mit mindestens drei Ecken, so ist G²Hamiltonsch.

Als Anwendung dieses Satzes von Fleischner haben verschiedene Autoren im gleichen Jahr nachweisen können, daß G² sogar Hamilton-zusammenhängend ist, falls G keine Artikulation besitzt. Darüber hinaus hat L. Nebeský 1980 bemerkt, daß man aus Fleischners Satz leicht das nächste Resultat folgern kann.

Ist G ein beliebiger Graph mit mindestens drei Ecken, so ist G²oder (\(\bar{G}\))²Hamiltonsch, wobei \(\bar{G}\)der Komplementärgraph von G ist.