[Discrete Mathematics] Euler Circuits and Euler Trails

We talk about euler circuits, euler trails, and do a proof.

*--Playlists--*

*--Recommended Textbooks--*

In this video we discuss Euler Circuits and Euler Trails, as well as go over the proof of such.

Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.

[emirz]

Sick channel, dudeee. Saved my discrete course.

[mistersir]

man you cracked me up so hard at 24:41. "we fuc* low"

[Sspectator]

Theorem: If the sum of degrees is even in a graph, and it is connected it is an Euler Circuit.
Axiom 1: If the sum of degrees is even in a graph, removing a circuit removes an even amount of degrees.
Axiom 2: If the sum of degrees is even in a graph, subgraphs are even and connected.
Axiom 3: If the sum of degrees is even in a graph, and it is connected, a circuit can be formed, not necessarily an Euler Circuit.
Axiom 4: Removing a subgraph that is a circuit removes an even amount of degrees from the degree sum of the graph.
Axiom 5: An Euler Circuit has even degrees and is connected.
IH: Assume the theorem has been proven for all graphs with n<=k edges true. Assume a graph where n=k+1 edges has even degrees and is connected.
Step 1: Axiom 3.
Case 1: The circuit turns out to be an Euler Circuit which immediately proves the graph is consistent with the theorem.
Case 2: The circuit does not turn out to be an Euler Circuit.
Step 2: If Case 2, decompose the graph of the circuit that has been created.
Step 3: Axiom 4. Axiom 2. Axiom 5 true for all e<=k edges.
Step 4: Upon reconstructing the circuit, the circuit will coincide with Euler Circuits which proves that if the graph has even degrees and is connected for k+1 edges, it is an Euler Circuit

Am I overthinking it? Not sure if I actually understand the proof.

[maycodes]

THank you so much, I was doing graph in computer science, got much clarity

[zainabqureshi]

can you make a video on hamilton paths and circuits

[eldarguliyev]

What textbook are you talking about?Which one would you suggest?

[kaushikdr]

How do you know how many vertices to use for the base case?

[mohitjha]

Euler Circuit can work for disconnected graphs if all the edges are in same component.

[vivekkapoor]

8 bitstring requires |v|=4 ? I did'nt get that. can u plz explain how? what bit strings r u talking about?

[usamabinmuzaffar]

I am really confused about the proof for Euler Circuits here... I couldn't understand the inductive hypothesis... So we assume that we have a graph with 'k' edges or less then 'k' edges has an Euler Circuit, cool... But when we do 'k+1', that breaks the conditions of an Euler Circuit as the degrees for the two vertices that the edge is connected between is not even anymore... And that brings the case of 'k-1' as well... How does the degree of each vertex still even?

[JoCS]

I don’t get to understand how someone can come up with that solution (the wheel problem). I understand the explanation but how to come up with it?

[farshedadib]

For the euler circuit of the rotating drum, why did you name the vertices 10, 11, 01, and 00?

[robharwood]

Probably could have started your base case for the Euler circuit proof with Case(k<=0) ==> Case(k<=1), where base case k=0 is just a single node with no edges (which still fits the definition of having Euler circuit (the trivial circuit)).