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
Each vertex accounts for two bits. This is an application of something called hypercube graphs. Read the section titled "construction" to see how binary numbers are allocated to each vertex here: en.wikipedia.org/wiki/Hypercube_graph
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?
e=k+1, you are adding an edge. but that edge must also satisfy (1) and (2), must be connected and even degree, the vertex you add will have have a way in and a way out for sure, since it must also have even degree
Hi there, you look like someone who understands the proof. I didn't understand how the reconstruction part of the proof proves that e=K+1 is true. Could you explain this to me please?
We remove an Euler Circuit and prove that the graph consists of smaller Euler Circuit Components. When you retrace the circuit you removed, you know that each time you encounter a vertex connected to another Euler Circuit Component you can take that circuit to return to your current vertex without traversing an edge twice (since the Euler Circuit Components have an even number of edges) and continue on your path. Thus when moving through the graph again you have shown that it is true for e = k + 1 since there is an Euler Circuit that you've discovered through the entire graph (which has k+1 edges).
![[Discrete Mathematics] Planar Graphs](http://i.ytimg.com/vi/ETtXKpfBWNI/mqdefault.jpg)
![[Discrete Mathematics] Planar Graphs](/img/tr.png)
![[Discrete Mathematics] Hamilton Cycles](http://i.ytimg.com/vi/t_6VByupc1U/mqdefault.jpg)
![[Discrete Mathematics] Vertex Degree and Regular Graphs](/img/1.gif)
Sick channel, dudeee. Saved my discrete course.
man you cracked me up so hard at 24:41. "we fuc* low"
Duuude what even is up with the audio at that part.
THank you so much, I was doing graph in computer science, got much clarity
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
you saved my degree thanks lot
lol
What textbook are you talking about?Which one would you suggest?
Well taught mate!
23:10 that is a beautiful graph
How do you know how many vertices to use for the base case?
Helped a lot thanks
can you make a video on hamilton paths and circuits
Thank you
Euler Circuit can work for disconnected graphs if all the edges are in same component.
8 bitstring requires |v|=4 ? I did'nt get that. can u plz explain how? what bit strings r u talking about?
Do you know about the bitstring? It is a word containing 0s and 1s. But I don't know why it requires 4 vertices either.
Each vertex accounts for two bits. This is an application of something called hypercube graphs. Read the section titled "construction" to see how binary numbers are allocated to each vertex here: en.wikipedia.org/wiki/Hypercube_graph
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?
e=k+1, you are adding an edge. but that edge must also satisfy (1) and (2), must be connected and even degree, the vertex you add will have have a way in and a way out for sure, since it must also have even degree
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?
For the euler circuit of the rotating drum, why did you name the vertices 10, 11, 01, and 00?
Farshed Adib this comes from the hypercube, see the video 'vertex degree and regular graphs' at about 11 minutes.
Superb 👌👌👌👌👌
Probably could have started your base case for the Euler circuit proof with Case(k Case(k
Hi there, you look like someone who understands the proof. I didn't understand how the reconstruction part of the proof proves that e=K+1 is true. Could you explain this to me please?
We remove an Euler Circuit and prove that the graph consists of smaller Euler Circuit Components. When you retrace the circuit you removed, you know that each time you encounter a vertex connected to another Euler Circuit Component you can take that circuit to return to your current vertex without traversing an edge twice (since the Euler Circuit Components have an even number of edges) and continue on your path. Thus when moving through the graph again you have shown that it is true for e = k + 1 since there is an Euler Circuit that you've discovered through the entire graph (which has k+1 edges).
i cant take it anymore
i found theorems so boring