NOTE: Seven Bridges of Königsberg and Eulerian graph

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.

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.

In Complete graph

A complete graph is a graph with each pair of graph vertices is connected by an edge. The complete graph with nnn graph vertices is denoted by KnK_nKn​. Each vertex degree is n−1n-1n−1, therefore, we can know when nnn is an odd number, KnK_nKn​ is an Eulerian graph.

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 ppp and qqq graph vertices in the two sets, the complete bipartite graph is denoted K(p,q)K_(p,q)K(​p,q). Since the vertices in set ppp must connect every vertex in set qqq, vice in versa, therefore, the only way to be a Eulerian graph is to make sure ppp and qqq both are even numbers.