NOTE: Seven Bridges of Königsberg and Eulerian graph
1. Seven Bridges of Königsberg
The seven bridges of Königsberg is a notable problem in mathematics. The following picture shows the actual layer of the seven bridges.
And we can use a graph version to simplify the problem.
Euler found, a
walkthrough of a graph, traversing every edges exactly once, depends on
the degrees of
the nodes(vertex). The graph must be
connected
and have exactly zero or two nodes of odd degree.
This walk called Eulerian path or Euler walk in his honor.
2. Eulerian circuit
Now we know what's Eulerian path. But what's Eulerian circuit? Eulerian circuit is a Eulerian trail that can start from a node and end at the same node. To make this, must have no nodes of odd degree in graph, because if there are nodes of odd degree, then any Eulerian path will start at one of them and end at the other.
2.1. In Complete graph
A complete graph is a graph with each pair of graph vertices is connected by an edge. The complete graph with \(n\) graph vertices is denoted by \(K_n\). Each vertex degree is \(n-1\), therefore, we can know when \(n\) is an odd number, \(K_n\) is an Eulerian graph.
2.2. In Complete bipartite graph
Complete bipartite graph, also calls complete bicolored graph or Complete bigraph. It is a bipartite graph such that every graph vertices in the two sets are adjacent. If there are \(p\) and \(q\) graph vertices in the two sets, the complete bipartite graph is denoted \(K_(p,q)\). Since the vertices in set \(p\) must connect every vertex in set \(q\), vice in versa, therefore, the only way to be a Eulerian graph is to make sure \(p\) and \(q\) both are even numbers.