In the 18th century, the city of Königsberg was traversed by the river Pregel, that divided the land areas into 4 distinct areas connected by seven bridges, a key puzzle that the residents of the city wondered about was whether you could visit all land areas by crossing every bridge exactly once and ending up where you started.
It was Leonhard Euler, the famous Mathematician that solved this puzzle by relying on connectivity rather than geography, his approach of modeling the problem by a graph birthed what would later be called Graph theory, the main subject of these series of courses.
The city as you can see in the map, can be modeled by a graph, here is its representation:
The property of a graph being able to be traversed by visiting its edges exactly once and ending up at the starting position is termed "Eulerian", when this circuit exists in a graph, it is called an "Eulerian circuit", when a similar circuit exists but you don't end up in your starting position, the circuit is called "Semi-Eulerian" and so is the graph.
A graph $G$ contains a cycle if the degree of each vertex is greater than or equals 2.
$\textit{Proof}$: We start by a random vertex, given our hypothesis, the vertex has at least 2 neighbors, without loss of generality let's suppose that he only has two neighbors, we start a path going from one of the neighbors and then we keep going until we reach the other neighbor and then we finish the cycle by ending up at the first vertex.
A connected graph is Eulerian if and only if every node has an even degree.
$\textit{Proof}$:
$\Rightarrow$): Given an Eulerian circuit of $G$, each visited node adds 2 to it's degree since each edge occurs exactly once in the Eulerian circuit and therfore each node has an even degree.
$\Leftarrow$): We will procede by induction on the number of edges of $G$, since $G$ is connected each node has a degree greater or equal than 2, therefore using the lemma, we know that $G$ contains a cycle $C$, if the cycle contains every edge, we're good, otherwise, we consider the graph we obtain by removing from $G$ the edges of $C$ to form a graph $H$ with fewer edges than $G$ and in which each vertex still has even degree.
Given our hypothesis, all components of $H$ has an Eulerian trail and since each component of H has at least one node in common with $C$, by connectedness, we obtain the required Eulerian trail of $G$ by following the edges of $C$ until a non-isolated node of $H$ is reached, following the Eulerian path of the component of $H$ that contains that node, and then continuing along the edges of $C$ until we reach a node belonging to another component of $H$, and so on until we reach the initial node.
