1.1.1. Definition of Euler Circuit and Euler Path

An Euler circuit is a simple circuit which contains every edge of the graph. Since it is a circuit, that means the starting point and the end point of the trail or the tour will be the same, meaning you have to start at the same vertex and you have to end at the same vertex in the tour. It is simple in the sense that the edges are not allowed to be repeated. An Euler circuit is a special type of simple circuit that contains every edge of the graph; no edge of the graph will be absent if the circuit exists. If you have an Euler circuit in your graph, then the graph is called an Eulerian graph.

An Euler circuit encompasses navigating through every edge of a graph exactly once while starting and finishing at the same point. To envision this, imagine riding a bike on every street in a neighborhood without re-riding on any street and returning to your home. To fulfill this condition, the path must not pass over any edge more than once, ensuring every street (edge) is included in the ride.

Consider a mail carrier assigned to deliver mail in a neighborhood. If the carrier must traverse every street without passing any street twice and must end their route at the same place they started, this mirrors the requirement of completing an Euler circuit.

An Euler path is a simple path which contains every edge of the graph. The key difference between an Euler path and an Euler circuit is that, in the case of the Euler path, the starting point and the end point are not the same. However, it remains a simple path, meaning no edges are allowed to be repeated.

An Euler path allows traversal through every edge of a graph exactly once but does not require that you return to the start point. For instance, after delivering mail on every street, the mail carrier could finish their route at a different address, say a friend’s house, marking the conclusion of their day’s work.

Imagine a person walking through a park that has several paths. They start walking at one end of the park, using each path to explore every area of the park. Not worrying about returning to the starting point, they finish at a different spot where they meet friends, which corresponds to completing an Euler path.

For a graph to have an Euler circuit, every vertex must have an even degree. Conversely, a graph can have an Euler path if exactly two vertices have an odd degree, while all other vertices must be of even degree.

The degree of a vertex refers to the number of edges connected to it. For an Euler circuit where you start and end at the same vertex, you must enter and leave every vertex an even number of times. If a vertex has an odd degree, that means you will either start or finish at that vertex, disallowing a complete round. An Euler path's requirement for two odd vertices indicates that you can enter one vertex and exit another without needing to balance out to form an Euler circuit.

Consider a delivery truck that must make a series of stops (vertices) to deliver packages (edges). If the truck can only finish its route at the warehouse (one odd vertex), it can pick up packages from there; similarly, if two delivery points (like neighboring houses) are unvisited after delivery, these will register as odd vertices. Thus, the truck can successfully complete its deliveries without having to balance out all stops.

--