You can trace a path in the graph by taking a pencil, starting at one of the vertices and drawing some of the edges of the graph without lifting your pencil off the paper. A path is simply a sequence of vertices where each vertex is connected by a line to the next one in the sequence. A circuit is any path in the graph which begins and ends at the same vertex.

Two special types of circuits are Eulerian circuits, named after Leonard Euler (1707 to 1783), and Hamiltonian circuits named after (William Rowan Hamilton (1805 to 1865). The whole subject of graph theory started with Euler and the famous Konisberg Bridge Problem.

An Eulerian circuit passes along each edge once and only once, and a Hamiltonian circuit visits each vertex once and only once. Both are useful in applications; the Hamiltonian circuits when it is required to visit each vertex (say every customer, every supply depot or every town) and the Eulerian circuits when it is required to travel along all the connecting edges (say all the streets in a town to collect the garbage). Note that for a Hamiltonian circuit it is not necessary to travel along each edge.

Here are two graphs, the first contains an Eulerian circuit but no Hamiltonian circuits and the second contains a Hamiltonian circuit but no Eulerian circuits. If you find it difficult to remember which is which just think E for edge and E for Euler. Can you draw for yourself other simple graphs which have one sort of circuit in them and not the other?

Conditions for there to be Eulerian circuits are well know but in general it is a difficult problem to decide when a given graph has a Hamiltonian circuit. Finding conditions for the existence of Hamiltonian circuits is an unsolved problem.

The degree of a vertex is the number of edges joining onto that vertex, and vertices are said to be odd or even according to whether the degree is odd or even. Euler circuits exist only in networks where there are no odd vertices, that is where all the vertices have an even number of edges ending there.

Two edges are used each time the path visits and leaves a vertex because the circuit must use each edge only once. It follows that if the graph has an odd vertex then that vertex must be the start or end of the path and, as a circuit starts and ends at the same vertex, for a circuit to exist all the vertices must be even. When there are two odd vertices a walk can take place that traverses each edge exactly once but this will not be a circuit.

Can you think why it is impossible to draw any graph with an odd number of odd vertices (e.g. one odd vertex)? Well the reason is that each edge has two ends so the total number of endings is even, so the sum of the degrees of all the vertices in a graph must be even, so there cannot be an odd number of odd vertices.

Here is a simple puzzle, which we call the Prime Puzzle, for you to solve that uses and illustrates Hamiltonian circuits. Each of the following numbers is the product of exactly three prime factors and you have to arrange them in a sequence so that any two successive numbers in the sequence have exactly one common factor. The numbers are $222$, $255$, $385$, $874$, $2821$, $4199$, $11803$ and $20677$ and we have used only the first twelve prime numbers. First factorize the numbers, next start to draw the graph which will have $8$ vertices, one for each number. Take one number on a vertex and draw three edges from it and label them, one for each factor. Now attach the appropriate numbers at the ends of these edges. Repeat the procedure until the graph is complete. Any two vertices are joined by an edge if and only if they have a common factor. You should have eight vertices and twelve edges and this should suggest a neat way to draw the graph. You may wish to re-draw the graph so that the edges do not cross except at the eight vertices. The graph will be one where it is easy to find a Hamiltonian circuit and this circuit gives you the solution to the problem.

Here is a similar but well known puzzle invented by Peterson where you have to arrange the ten cards in a loop so that each card has exactly one letter in common with each adjacent card. The words are HUT, WIT, SAW, CAR, CUB, MOB, DIM, RED, SON, HEN. The arrangement shown in the diagram looks very nearly correct but the words SON and RED do not match. If you try to solve the puzzle by re-arranging the cards you will not succeed because it is impossible. Now replace SON by SUN and HUT by HOT and the puzzle can be solved. The explanation is contained in the following two graphs.