Fig. 2
As you can see the problem now looks much simpler and one could attempt to solve by just using a pencil and going around the lines looking for a solution but to find a systematic approach to is incredibly tedious laborious. Euler devised a new notion; degree of nodes. The Degree of Node is the number of connections or the node has to other nodes. Euler said that any graph can be fully crossed with each edge crossing exactly once if it had, zero or exactly two nodes with odd degrees.
When a graph shows this property it is called, Eulerian path. Using this we know now that exactly two nodes must be at the start and end of the circuit. If there an even number of nodes then we can cross the node and not turn back on ourselves i.e. not cross the node again. In the bridges example, the graph has just 4 nodes, with each node having an odd degree therefore Eular came to the conclusion that the bridges cannot be crossed without repetition.
Suppose you have an undirected graph, G. A circuit that goes through each edge of G and passes each node is an Eulerian circuit. A circuit passes each edge of the graph G must cross each node; however the exception is when there are isolated nodes, meaning in this situation not all nodes are passed. Thus an Eulerian graph does not have any isolated nodes. A node however may be visited multiple times, as long as each edge is crossed once. 5
An Eulerian circuit is an Eulerian path, which was defined earlier, but also starts and ends on the same vertex.
There are a number of properties for Eulerian circuits
- A connected undirected graph is Eulerian if and only if every graph vertex has an even degree.
- An undirected graph is Eulerian if it is connected and can be decomposed into edge-disjoint cycles.
- If an undirected graph G is Eulerian then its line graph L(G) is Eulerian too.
- A directed graph is Eulerian iff it is strongly connected and every vertex has equal in degree and out degree.
- A directed graph is Eulerian iff it is strongly connected and can be decomposed into edge-disjoint directed cycles.
-
An undirected graph is traversable if it is connected and at most two vertices in the graph are of odd degree.
Euler founded graph theory which in turn has now seen its way in DNA sequencing through Eulerian circuits and the properties mentioned above in bioinformatics. This shows the importance of solving seemingly futile problems into something which is now beneficial to scientific research.
http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
http://www.jcu.edu/math/vignettes/bridges.htm
Fig 1: http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
Fig 2: http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
http://www.jcu.edu/math/vignettes/bridges.htm
http://en.wikipedia.org/wiki/Degree_distribution
http://en.wikipedia.org/wiki/Eulerian_path
Directly pasted from http://en.wikipedia.org/wiki/Eulerian_path#Properties