Subscribe to the weekly news from TrueShelf


The cube of a connected graph is hamiltonian

Prove that the vertices of any connected graph \(G\) can be listed in a cyclic order so that the distance in \(G\) of every two consecutive vertices is at most \(3\).

Moreover, show that this can be done in linear time.

Related Content