1. Euler Path and Euler Circuit

So, let us start with the definition of Euler circuit and Euler path. So, imagine that you are given a graph then an Euler circuit is a simple circuit which contains every edge of the graph. So, since it is a circuit that means the starting point and the end point of the trail or the tour will be the same that means you have to start at the same vertex and you have to end at the same vertex in the tour.

And it is simple in the sense that during the tour the edges are not allowed to be repeated. So, it is a special type of simple circuit in the sense that it contains every edge of the graph; no edge of the graph will be absent in this simple circuit if you have the existence of such a simple circuit and the circuit will be called as an Euler circuit. And if you have an Euler circuit in your graph then the graph will be called as an Eulerian graph.

Whereas an Euler path is a simple path which contains every edge of the graph so the difference between Euler path and Euler circuit is that in the case of Euler path your starting point and end point are not same because it is just a path. However it is still simple and hence the edges are not allowed to be repeated. Whereas in the case of Euler circuit edges are not allowed to be repeated but you also need the fact that the starting point and end point should be the same.

An Euler circuit is a closed loop in a graph that visits every edge exactly once and returns to the starting point, while an Euler path is a trail that visits every edge exactly once but does not necessarily return to the starting vertex. The key difference is that an Euler circuit starts and ends at the same vertex, while an Euler path starts at one vertex and ends at another. Both paths must not repeat any edges.

Think of it like a mail carrier's route: an Euler circuit would mean the carrier starts and ends at the post office while visiting every street once, while an Euler path would be like a delivery route that starts at the post office and ends at a client's house, covering all streets without returning.

So, let us see some examples of both these concepts. So, imagine this is a graph given to you then this graph has an Euler circuit and hence this graph will be an Eulerian graph. So, if you follow the tour along the blue edges or the blue arrows that gives you an Euler circuit. So, for instance suppose I start at e in fact you can start at any vertex and I first go from e to d that takes care of this edge then I go from d to c that takes care of this edge between d and c. Then I go from c to f that takes care of this edge then from f I go to g that takes care of the edge between the node f and g then I go from g to c that takes care of this edge. And then finally I stop my tour by traversing the edge between c and e. So, you can see I started at e and ended my trip at e and in my tour all the edges of the graph are covered and no edge is repeated. Hence this is an example of an Euler circuit.

Whereas if you see this graph then it is easy to verify here that this graph does not have any Euler circuit you start at any vertex it is impossible to make a tour starting at the same vertex and ending at the same vertex and traversing every edge of the graph exactly once and without repeating any edge that is not possible.

The lecturer illustrates the concepts of Euler circuits and paths through specific examples. In the first graph, a tour is shown that starts and ends at the same vertex, visiting all edges, thus confirming it contains an Euler circuit and is classified as an Eulerian graph. Conversely, the second graph cannot accommodate an Euler circuit as no tour can fulfill the requirement to start and end at the same vertex while visiting all edges without repeating any.

Consider the difference like traveling a city: if you can follow a route to visit every street and return to your starting point without retracing steps, that's akin to an Euler circuit. However, if you are unable to return to the start after visiting all streets, it represents a scenario without an Euler circuit, much like a trip that ends at an airport rather than at your home.

So, Euler gave a very simple necessary and sufficient condition according to which you can verify easily whether a given arbitrary graph has an Euler circuit or not. So, the theorem statement is the following. Imagine you are given a connected graph that is important and your graph need not be a simple graph it can be a multi graph by multi graph I mean that between the same pair of vertices you might have multiple edges.

So, the graph need not be a simple graph but still I can define the notion of Euler circuit and Euler path even for multi graph. So, imagine you are given a connected undirected graph which is a multi graph and the graph has at least 2 nodes because if my graph is just a single node then again the notion of Euler circuit does not make much sense there. So, imagine you are given a multi graph which is connected and it has at least 2 nodes. Then what Euler proved is that the graph will have an Euler circuit if and only if each of the vertices in the graph has even degree.

Euler's theorem states that a connected graph has an Euler circuit if all vertices have an even degree. This is essential because an Euler circuit requires every vertex to be entered and exited equally. Therefore, if any vertex is odd, it suggests that there must be an entrance or exit that does not match, making a closed loop impossible.

Imagine a party where every friend must say goodbye after visiting each other; if one friend leaves before saying goodbye to the last, it disrupts the order. This illustrates how an odd number of 'entrances and exits' (edges) at a vertex prevents forming an Euler circuit.

And this condition is both necessary condition as well as a sufficient condition because this is an if and only if statement. So, we will prove both the necessity condition as well as the sufficient condition. So, let us first prove the necessity condition namely the only if part. And for that we have to show the following implication we have to prove that if your graph has an Euler circuit then it implies that each vertex of the graph has even degree you cannot have any vertex in the graph which has an odd degree.

To prove the necessity condition, it needs to be shown that if there is an Euler circuit, each vertex in the graph must have an even degree. The argument includes analyzing how each time we enter and exit a vertex through an edge, it contributes to the degree count. Hence, if the circuit starts and ends at the same vertex, that vertex's degree must be even, and this reasoning applies to all vertices present in the circuit.

Think of guests at a dinner party leaving through pairs of doors; if everyone exits through the front door (even degree), they don’t disrupt the balance of exits. If one person exits alone without a returning match (odd degree), it throws off the party representation just like creating imbalance in the graph.

Now we will prove the sufficiency condition if part and for that we have to show the following: I have to show that if you are given a connected multi graph where all the vertices have even degree then there exists at least 1 Euler circuit in your graph there might be multiple Euler circuits also possible in your graph but at least 1 Euler circuit is definitely there. And for proving the sufficiency condition I will discuss here an algorithm called as Fleury’s algorithm.

The sufficiency condition states that if every vertex in a connected multi graph has an even degree, then there is at least one Euler circuit. Fleury’s Algorithm helps to find this circuit by systematically traversing edges while keeping the conditions of not revisiting edges and ensuring to prefer non-cut edges until no other choice exists. This ensures that all edges are covered, fulfilling the definition of an Euler circuit.

Imagine you are walking through a park and want to avoid crossing the same path twice to enjoy the scenery. Fleury’s algorithm dictates you to first pick paths that don't lead you into dead ends (cut edges), ensuring you traverse the entire park without retracing your steps.

So that was the simple characterization of Euler circuit. Now let us quickly prove a characterization of Euler path. So, the characterization of Euler path is that in your graph there should be exactly 2 vertices of odd degree and remaining all vertices should have even degree.

For a graph to have an Euler path, there must be exactly two vertices with odd degrees, while all others must have even degrees. This ensures that you can start at one of the odd-degree nodes and end at the other, as the odd degrees represent the entrances or exits that don’t have a matching pair.

Consider a street in a city where each street ends at a house: having two houses (odd vertices) with no neighbors on one side allows beginning there and finishing at the other when delivering pizza. All other streets (even vertices) provide the necessary balance.

So that brings me to the end of this lecture. These are the reference used for today’s lecture, I also follow some of the notes from Prof. Choudum’s NPTEL lecture on graph theory specially for the proof of correctness of Fleury’s algorithm. So, just to summarize in this lecture we saw the definition of Euler circuit, Euler path and we proved the necessary and sufficient condition for the existence of Euler circuit and Euler path in the graph, thank you.

The lecture concludes by summarizing key concepts such as Euler circuits and paths, along with the conditions that allow for their existence. Reinforcing understanding ensures students are aware of essential details covered in the session.

Think of the lecture as teaching you the rules of a new game, where now you can confidently navigate through the gameboard understanding these 'Euler' pathways and ensuring that every piece is placed correctly without 'repeating' steps—like performing a successful round of a circuit.

--