Electoral hex redux and African colonialism

At Gil Kalai's blog I came across a map in which counties which voted Democratic in some election are colored blue, and counties which voted Republican are colored red. (It is not the 2008 presidential election map, or at least it doesn't match Mark Newman's map.)

Anyway, Kalai suggests "hex voting" -- like the game of Hex, the Republicans win if there's a continuous path in red counties from north to south, and the Democrats win if there's a continuous path of blue counties from east to west. (In the map he gives, the Republicans win, but only barely -- there are some places where the red region is only one county wide.)

It turns out that the British and French played a similar game in Africa early in the last century; here's a map of European claims to Africa in 1913, in which the British were attempting to create a continuous path of red (British) colonies from north to south, and the French were attempting to create a continuous path of blue (French) colonies from east to west. (At least, that's how the Wikipedia article on Cecil Rhodes puts it.)

The five bridges of Kaliningrad

In 1736 Euler solved the following problem: the city of Königsberg is set on both sides of the Pregel river and on two islands between them. There are bridges connecting the various landmasses; is it possible to walk around the city in such a way that you cross each bridge exactly once? The answer is no; (the network of landmasses and bridges in) Königsberg didn't have an Eulerian path. In order to have an Eulerian path the graph corresponding to this network must have zero or two nodes of odd degree; that is, if we consider the number of bridges on each landmass, exactly zero or two of these numbers can be odd. In Königsberg all four degrees were odd.

But the bridges were bombed in World War II, the city was renamed Kaliningrad, and only five of them were rebuilt. These are bridges connecting each of the islands to each of the shores, and a brige connecting the two islands. As you can see, there are three bridges on each island and two on each shore of the river; two of these numbers are odd, so there exists an Eulerian path. It's still somewhat useless, because you have to start on one island and end on the other.

Here's a map of the route, from Microsiervos (in Spanish), and here are some pictures that some folks took when they were visiting Kaliningrad and actually doing this.

I also remember once seeing the analogous network for New York City (the relevant landmasses being Manhattan, Long Island, Staten Island, the Bronx, and New Jersey), which has a lot of bridges, with the question of whether that network had an Eulerian path. I don't remember the answer. I also think it wouldn't be as much fun; New York has lots of traffic and is much larger than Kaliningrad.