The beginning of topology is often traced to Euler’s solution of a puzzle, the Bridges of Königsberg. The problem posed was to follow a path through the Prussian city that crossed all seven bridges exactly once.
Euler proved that the problem has no solution. He drastically simplifying it by replacing the geographical context by a simple graph with a vertex for each land-mass and edges for each bridge.
Euler’s Gem
A remarkable general result was discovered by Euler. For any plane graph, if 
This is a special case of a much more general result. It also holds for polyhedra in 3-space and for polytopes in higher dimensional spaces. An excellent account of what is called ‘Euler’s Gem’ is given in the book of David Richeson (2008).
In the case of the bridges problem, we have 
Eulerian Paths and Circuits
An Eulerian path is a path that traverses every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends on the same vertex. These concepts were first considered by Leonhard Euler 1n 1736, in connection with the problem of the Seven Bridges of Königsberg.
The degree of a vertex is the number of edges linked to it. Euler proved that a necessary condition for the existence of an Eulerian circuit is that all vertices in the graph have an even degree. This result is now known as Euler’s Theorem: A connected graph has an Euler circuit if and only if every vertex has even degree.
Euler’s result is easy to understand: on an Eulerian path, each ‘incoming’ link at a vertex must have a corresponding ‘outgoing’ link. Thus, the total number of links must be an even number, or the degree of the vertex must be even. Counting the edges linking to each vertex in the Euler’s graph (Figure above, left panel), we find that three vertices have degree 3 while one has degree 5.
Hamiltonian Paths and Circuits
A Hamiltonian path is a path that visits each vertex exactly once. A Hamiltonian circuit is a Hamiltonian path that starts and ends at the same vertex (is a closed circuit). A graph that contains a Hamiltonian circuit is called a Hamiltonian graph.
Clearly, Euler’s Königsberg graph is a Hamiltonian graph: by tracing a closed path around the outer edges, we pass through all vertices and arrive back at the starting point.
The Dual Graph
For every plane graph in the plane, there is another graph called its dual. The dual graph has a vertex for each face of the original graph and an edge for each pair of faces separated by an edge. When the same face appears on both sides of an edge, the dual graph has a self-loop, an edge connecting a vertex to itself.
There are often many different representations of a graph in the plane. Although clearly distinct, they are topologically equivalent. In the figure below we show two such representations of the dual graph for the Königsberg Bridges Problem. They are both homeomorphic to the graph in the centre panel of the Figure above. All have 
Dipole Graphs and Cycle Graphs
A cycle graph is a graph consisting of a single cycle, a number of vertices connected in a closed chain. The order-
A dipole graph consists of two vertices connected by two or more edges. An order-
The dual graph of the order-
Concluding remarks
The concept of dual graph is valuable in many contexts. There are many theorems concerning graphs and their duals. For example, a standard result of graph theory states that a connected planar graph is Eulerian if and only if its dual graph is bipartite.
Duality is relevant in a broader context than for planar graphs and has been studied for centuries. The duality of convex polyhedra was recognized by Johannes Kepler in his 1619 book Harmonices Mundi.
In a future post, we will look at the Tonnetz, a graphical representation of the notes in the chromatic scale and — through its dual — of the relationship between the major thirds and other chords.
Sources
ThatsMaths 