1.2.1. Proof of Correctness

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. The theorem states that a connected graph will have an Euler circuit if and only if each of the vertices in the graph has an even degree. This condition is both necessary and sufficient.

This chunk introduces the fundamental theorem related to Euler circuits. It states that for a connected graph, the existence of an Euler circuit (a path that visits every edge exactly once and returns to the starting vertex) is dependent on each vertex having an even degree (the number of edges incident to the vertex must be even). If any vertex has an odd degree, then an Euler circuit cannot exist. The contradiction arises from the need to leave and re-enter vertices, which would necessitate even degrees.

Imagine a city connected by roads where each intersection (vertex) should have an even number of roads leading to it. If one intersection only has one road leading away (odd degree), then you've got a dead end when you arrive there - you can’t complete a circuit.

Assume a graph has an Euler circuit and denote the starting and ending vertex as 'a'. In this case, every edge entering 'a' (first edge and every edge coming back) contributes to its degree. Although we can move in and out of 'a', each entry-exit cycle means it must be traversed an even number of times, leading us to conclude that 'a' must have an even degree. This reasoning applies to all vertices, confirming the requirement for even degrees.

Here, we are required to prove that if the graph contains an Euler circuit, all vertices must have even degrees. By following the tour from the start to the end, every edge incident to the starting point 'a' is used to connect to other vertices and eventually returns back, increasing its degree. This argument can be extended to each vertex involved in the circuit, leading to the conclusion that they all must exhibit this property.

Think of a dance where everyone must enter and exit the dance floor through the same doors (vertices). If one person exits and never returns through the same door, someone else must eventually come back to that door, contributing to the degree of the doorway. This ensures the door is evenly used, similar to ensuring every vertex has an even degree.

To show the converse, consider a connected graph where all vertices are guaranteed to have even degrees. Using Fleury's algorithm ensures we can construct an Euler circuit within such a graph as it preserves the principle of avoiding cut edges until absolutely necessary. This iterative process will yield an Euler circuit.

In this part, we illustrate how having all vertices of even degree guarantees the possibility of constructing an Euler circuit. By employing Fleury's Algorithm, which emphasizes careful selection of edges, we can iteratively travel through the graph without breaking the circuit. This iterative building of the path ensures we explore all edges exactly once while respecting the circuit nature.

Imagine someone walking through a city, always turning at intersections but avoiding roads that lead into isolated alleyways unless all other options are exhausted. This method guarantees the person will return to their starting point without retracing steps over the same roads, analogous to confirming an Euler circuit in graph theory.

Fleury’s algorithm involves starting from any vertex and iteratively selecting edges to traverse while avoiding cut edges until there are no options left, ensuring all edges are covered. By maintaining a simple circuit and adapting the graph at each step, we ensure a complete tour is achieved.

This algorithm provides a systematic approach to finding Euler circuits in a graph by iterating through each edge strategically. By keeping track of how edges are traversed and carefully choosing which edges to travel along, we guarantee that the path respects the Euler conditions. The beauty of Fleury's algorithm lies in its flexibility and systematicity in covering all edges while maintaining structural integrity.

Think of a puzzle where you need to touch every piece (edge) given specific rules about how you can move (traverse). Fleury’s approach allows you to navigate the puzzle board without repeating movements unnecessarily while ensuring every piece is accounted for.

Following the above reasoning, if a graph is connected and all vertices have even degree, applying Fleury’s algorithm guarantees the outcome is an Euler circuit. Conversely, if there are exactly two vertices of odd degree, it indicates the presence of an Euler path but not a circuit.

This concluding chunk ties together our findings by reaffirming the criteria for Euler circuits and paths. It summarizes that even degree vertices lead to circuits, while having precisely two vertices of odd degree allows for an Euler path, which is a tour that doesn't return to its starting vertex. Hence, both conditions reinforce the governing theory of Eulerian paths and circuits.

It's like navigating a neighborhood where you can either take every street back to the starting point (Euler circuit) or just complete a route that leads you to an unexplored street and ends at a different point (Euler path). The paths exist based on how the intersections are set up.

--