최초의 GraphTheory문제. LeonhardEuler가 제기. Konigsberg는 서로 연결된 두섬을 가지고 있고 나머지 도시는 7개의 다리로 연결되었다. 강의 다른 부분으로는 어느 다리를 이용해서든지 도달할 수 있다. 어느 도시에서 출발하건 모든 다리를 물에 빠지지 않고 정확히 한번만 지나 갈수 있나?

이 문제를 풀기위해 Euler는 Graph표기를 발명했다. 그는 Konigsberg의 지도를 네 개의 정점을 그리고 일곱 개의 다리를 가진 간단한 그래프로 표현했다.

몇 쌍의 노드는 하나 이상의 edge로 연결되어있다. 도시들간에 하나 이상의 다리가 있는 것을 보면. 지도에서 모든 다리를 한번에 건너는 루트를 찾는 것은 그래프에서 모든 edge를 정확히 한번 지나는 통로를 찾는 것과 동일하다.

EulerTheorem : If a network has more than two odd vertices, it does not have an Euler path. If a network has two or less odd vertices, it has at least one Euler path.

SeeAlso http://mathforum.org/isaac/problems/bridges1.html