Section 3.2 Eulerian and Hamiltonian Graphs
It is no real problem to tell if a graph is Eulerian given a characterization using the degrees of the vertices (i.e. all even). We will create a random graph on a specified number of vertices and a given number of edges, identify its degree sequence and check for the existence of an Euler circuit. You can edit the cell below by removing the seed keyword and really get random graphs. We set the seed to make the example testable.
If you would like an actual Euler circuit, Sage can do that, too. You can get back the edges, with or without their labels, and you can also ask for a list of the vertices in the circuit. This function, and the query above, can be set to also investigate Eulerian paths.
It is a nice feature that Sage labels the vertices of the hypercubes with compact binary strings, aiding in recognizing the nature of the adjacencies. But if that makes some output too verbose for you, then you can consult the documentation for the .relabel() method of a graph to see how to make changes.
If existence and construction of Euler circuits is relatively straightforward computationally, the existence and construction of Hamiltonian circuits is another matter. But Sage is up to the task.
We will recycle our random graph from above. You can remove the seed, vary the number of edges, and perhaps add a check with the .is_connected() method so that you do not preclude the existence of a Hamiltonian circuit by using so few edges that the graph becomes disconnected.
Similar to the case for Euler circuits, we can ask for a Hamiltonian cycle when one exists. The nature of the output depends on the algorithm you use. We will specify the backtrack algorithm so as to get an ordered list of vertices (along with the result of .is_hamiltonian). If you use the tsp (Traveling Salesman Problem) algorithm, you will get back an actual subgraph that is the Hamiltonian cycle.
You could have Sage plot the random graph R for you and then trace out the Hamiltonian cycle as a check.