Professor Alex Scott on the Koenigsberg Problem
Professor Alex Scott OE, sometime KS and now Professor of Mathematics at the University of Oxford and Tutorial Fellow at Merton College, who gave the inaugural MathSoc talk some twelve years ago, spoke under the title ‘How to plan a walking tour’. He started off with Euler’s famous Seven Bridges of Koenigsberg problem: given the arrangement of bridges in C18 Koenigsberg, is it possible to go for a walk crossing each bridge exactly once and arrive back where one started? The question can be asked of an abstract graph consisting of nodes and edges joining the nodes: is there a circuit which uses every edge exactly once? Professor Scott proved that such an Eulerian circuit is possible provided the graph is connected and that each node has an even number of edges associated with it. We then looked at Hamiltonian circuits, where the aim is to visit all the nodes, not traverse all the edges. Establishing whether a graph has such a circuit is a hard problem, known to be in a class of hard problems known as NP-complete. Professor Scott finished off his talk by explaining to us the difference between P and NP problems, and by classifying the problems we had studied into these categories. Although much is known about these classes of problems, it is still unknown whether P=NP . This is one of the seven Millenium Prize Problems of the Clay Mathematics Institute: a proof or disproof is worth $1,000,000.
Timothy Khoury KS
