The travelling saleman

A problem similar to that of the Königsberg bridges was posed in 1859 by William Rowan Hamilton (1805 – 1865) (left), the inventor of quaternions.

Is it possible to traverse a graph while visiting each vertex exactly once?
No-one has yet solved this problem, known as the travelling salesman problem, although in 1972, Shen Lin produced an algorithm used to design telephone networks, which gives a solution which is close to optimum.

Exercise 1 Which of these two graphs is traversible? (Can you draw each of them without taking your pen from the page?) If the graph is traversible, find the path which visits every edge exactly once. This is called an Euler path.                                                                                                            Check