The Swiss mathematician Leonhard Euler (1707-1783) took this problem as a starting point of a general theory of graphs. That is, he first made a mathematical model of the problem. He denoted the four pieces of lands with "nodes" in a graph: So let 0 and 1 be the mainland and 2 be the larger island (with 5 bridges connecting it to the other pieces of land) and 3 be the smaller island (with 3 bridges connecting it to the other pieces of land). Now one could give for each node a list of nodes it was connected to, with a multiplicity factor telling how many bridges were there:

- To 2: 2; To 3: 1;
- To 2: 2; To 3: 1;
- To 0: 2; To 1: 2; To 3: 1;
- To 0: 1; To 1: 1; To 2: 1;

var a = new Array(); var a[0] = new Array(); a[0][2] = 2; a[0][3] = 1; var a[1] = new Array(); a[1][2] = 2; a[1][3] = 1; var a[2] = new Array(); a[2][0] = 2; a[2][1] = 2; a[2][3] = 1; var a[3] = new Array(); a[3][0] = 2; a[3][1] = 2; a[3][2] = 1;Euler analysed now that there are two situations.

- If the starting point and the end point of the trip are the same - this situation could be called a circuit - then for every node the sum of the connectives must be even, as each time the node is visited, the visitor comes in on one bridge and leaves on another bridge.
- If the starting point and the end point of the trip are different - this situation could be called a path - then there are two nodes which must have an odd number of bridges: The node where the trip stars and the node where the trip ends. All other nodes must have an even number of nodes.
- Furthermore, Euler observed that all nodes must be connected. Otherwise there would be two nodes i and j so that whenever one starts a trip at i one cannot reach node j in whatever way one is going. For example if there would only be an even number of bridges between 0 and 1 and also between 2 and 3 but no other bridges then one cannot go from 0 to 3, as all pathes starting at 0 can only visit the nodes 0 and 1.

The following Javascript programs check the conditions. First the program reach(i,a) lists in an array all the nodes which can be reached from i without caring whether a bridge is used once or several times.

function reach(i,a,b) { if (i in b) { return; } b[i] = 1; for (j in a[i]) { reach(j,a,b); } return; } ..... for (i in a) { b = new Array(); reach(i,a,b); for (j in a) { if (!(j in b)) { return("The graph "+display(a)+" is not connected."); } } } .....The function uses a subfunction "reach". Note that this function is recursive: when coming into a node i, it marks it as reached by making an entry into b and then visits all nodes j in recursive calls which are connected to i. Furthermore, it does this only in the case that i is not yeat marked as reached, in order to avoid that the program recursively visits a node and revisits it and revisits it and so on. The list of nodes reached from i in the graph a are then returned. In order to be sure that every node is visited, the main program has then to compare whether the nodes in b and in a are the same. In the current implementation, a loop checks whether from every i in a every node can be reached; however, it would be sufficient to check it only for one node i.

The second part to be checked is the Euler condition on the number of bridges - in graph theory they are called edges - for each node. For an Euler circuit, this number of edges has to be even in every node. The program part to do this is the following.

function euler(..) { .... for (i in a) { k = 0; for (j in a[i]) { k = k+a[i][j]; } if (k%2 == 1) { h = h+1; } } if (h == 0) { return("The graph "+display(a)+" has an Euler circuit."); } if (h == 2) { return("The graph "+display(a)+" has an Euler path."); } var t="The graph "+display(a)+" has "+h+" nodes with odd connections."); return(t); }One can compute the Euler circuit or Eulerpath with the following function which returns an array of the path (or circuit in the case that s == t) from s to t; note that the arrays a and u are parameters; a[i][j] says how many bridges there are between nodes i and j; u[i][j] says how many of these are already used and u[i][j] is 0 at the beginning. As the direction of the usage of the bridges does not matter, each usage must update u[i][j] as well as u[j][i]. The path is stored in v and w; v is the final part, w is the part which might still have to be checked on whether a self-loop from the nodes in w to itself through some bridges needs to be inserted in order to make the Euler path or circuit complete.

function findeuler(a,s,t,u) { var v = new Array(0); var w = new Array(0); var i = s; var j = 0; var k; w.push(i); var r; do { j = "new"; for (k in a[i]) { if (u[i][k] < a[i][k]) { j = k; } } if (j != "new") { w.push(j); u[i][j]++; u[j][i]++; i = j; } } while ((i != t) && (j != "new")) while (w.length > 0) { i = w.shift(); v.push(i); j = "new"; for (k in a[i]) { if (u[i][k] < a[i][k]) { j = k; } } if (j != "new") { u[i][j]++; u[j][i]++; r = findeuler(a,j,i,u); w = r.concat(w); } } return(v); }If you view the source of this page in Firefox (Webdevelopper, view source), you find all Javascript programs related to this topic in the begin of this file and can copy them into the Scratchpad to study them more in detail. You can click the below buttons in order to get sample graphs for each of the possible outcomes, the last button illustrates some checks which are done in order to make sure that the graph is coded in a consistent way (that is, if a[i][j] exists then a[j] should exist and a[i][j] should be equal to a[j][i] and so on).

function subhamilton(i,a,b) { var j; var k = 1; b[i] = 1; for (j in b) { if (b[j]==0) { k=0; } } if (k == 1) { b[i] = 0; return(0 in a[i]); } for (j in a[i]) { if ((b[j]==0)&&(k == 0)) { k = subhamilton(j,a,b); } } b[i] = 0; return(k); } .... function hamilton(..) { .... var b = new Array(); for (i in a) { b[i] = 0; } if (subhamilton(0,a,b) == 1) { return("The graph "+display(a)+" has a Hamiltonian circuit."); } else { return("The graph "+display(a)+" has no Hamiltonian circuit."); } }