Thank you for the helpful video! I had a little trouble at 6:00 but i realized that all you were doing was rearranging (e' = e - 1) and (v' = v - 1) into (e' + 1 = e) and (v' + 1 = v) and then plugged it into the earlier equation (e = v - 1)! It probably took me a bit because I am just a visual learner and I needed to see all the steps. (I'm also typing this out just in case anyone else has the same issue as me later on!)
Probably also worth reiterating that this is a proof around the theorem e = v-1. The final part of the proof begins from where e=v-1 is written. e' + 1 which is equivalent to e = v' + 1 which is equivalent to v then we - 1 (which is representing our hypothesis of e = v-1). Think of each line as a edging together closer and close to the proof. Note the +1-1 cancels out and we are left with e' + 1 = v' which essentially says for a tree if you need the number of vertices add 1 to the number of edges. In the final line we are essentially delivering the final proof statement that if we know the previous (for a tree if you need the number of vertices add 1 to the number of edges) then it is fair to conclude if we remove 1 from the total vertices we are left with the formula e' = v' - 1 essentially finishing the proof that to get the edges we deduct the 1 from the number of vertices. Sorry for the bad english I am at home sick.
These tutorials have really been very helpful! Thank you sir for explaining the concepts and making them crystal clear! I'm really surprised of the fact that u just have 15k subscribers u seriously deserve to have a lot more.
Awesome you can also use Eulers formula to prove a tree has n-1 edges since the region is 1(infinite space) and trees are planar r=e-v+2, r=1 & v=n . However I like the way you proved it makes more senser
@5:16 Whif the vertex has more than one edge coming outta it? well, the graph disconnects, but proving THAT complicates things. better unleash Euler's Bazooka (v-e+r=2, with r=1). giving the desired answer. I mean, what's the use of developing Euler's Bazooka (moar like Euler's Panzerfaust, amirite) if you don't use it?
Show by means of an example that a simple diagraph in which exactly one node has indegree 0 and every other node has indegree 1 is not necessary a directed tree?
@@Trevtutor That's true, but you glossed over that a bit. The proof didn't seem very robust as a result, IMO. I realize that you have limited time in a video when you're trying to cover material, but just trying to throw out some (hopefully) constructive criticism.
I am having difficulty with the proof by induction. The basis step talks about |e|=0. and then you show that if the property already holds for some tree, then it'll hold for a **smaller** tree. But this is not the same as the "k+1" step. for this proof to be complete, don't you need to start from the largest possible tree instead of the smallest possible tree?
Thanks! I am still a bit confused as to what is going on around time 6:05. The way I understand it, is that you apply the induction hypothesis to the bigger tree (using e'+1), and from that, you show about e'. by the way, my I ask which tools you're using to produce these beautiful videos? software? devices?
@@tryingtolearn2966 Really, it's just that if you assume the tree you're working with is consistent with e = v - 1, then by removing an edge, the resulting tree also seems to show the same properties. All you need to do is prove that this resulting tree actually does follow the hypothesis, and to prove that, you just need to remove an edge from it and prove that the next tree also follows it. Eventually, you'll stumble upon the base case tree that has already been proven to have the wanted consistency, which creates a chain reaction. Remember, all trees start out with 1 vertice. By adding an edge, you must also add a vertice that it will connect to, keeping the degrees of each individual vertice = 1.
![[Discrete Mathematics] Tree Directories and Traversals](http://i.ytimg.com/vi/z_OwSnFY_5s/mqdefault.jpg)
![[Discrete Mathematics] Tree Directories and Traversals](/img/tr.png)
![[Discrete Mathematics] Planar Graphs](/img/1.gif)
Thank you for the helpful video!
I had a little trouble at 6:00 but i realized that all you were doing was rearranging (e' = e - 1) and (v' = v - 1) into (e' + 1 = e) and (v' + 1 = v) and then plugged it into the earlier equation (e = v - 1)! It probably took me a bit because I am just a visual learner and I needed to see all the steps. (I'm also typing this out just in case anyone else has the same issue as me later on!)
Probably also worth reiterating that this is a proof around the theorem e = v-1. The final part of the proof begins from where e=v-1 is written. e' + 1 which is equivalent to e = v' + 1 which is equivalent to v then we - 1 (which is representing our hypothesis of e = v-1). Think of each line as a edging together closer and close to the proof. Note the +1-1 cancels out and we are left with e' + 1 = v' which essentially says for a tree if you need the number of vertices add 1 to the number of edges. In the final line we are essentially delivering the final proof statement that if we know the previous (for a tree if you need the number of vertices add 1 to the number of edges) then it is fair to conclude if we remove 1 from the total vertices we are left with the formula e' = v' - 1 essentially finishing the proof that to get the edges we deduct the 1 from the number of vertices. Sorry for the bad english I am at home sick.
These tutorials have really been very helpful! Thank you sir for explaining the concepts and making them crystal clear! I'm really surprised of the fact that u just have 15k subscribers u seriously deserve to have a lot more.
114k now :)
@@jagritiyadavv 209k now
@@andromedaghostgames hey babe
thanks a lot, it really helped me, thank u for giving so much of time in teaching all these topic.
I like everything bout this channel except : he doesn't make playlists and I can't find the order to watch the videos.
Awesome you can also use Eulers formula to prove a tree has n-1 edges since the region is 1(infinite space) and trees are planar r=e-v+2, r=1 & v=n . However I like the way you proved it makes more senser
if e >= 1 shouldnt there be at least two vertices instead of one?
It is not possible to create a tree with one vertex.
@@shubhochowdhury6898 Why not? A single vertex is a connected graph with no simple circuits.
@@lyndongingerich1482 Thats a loop, itself is a circuit... special type of circuit
@@wolfcompany2 Interesting. Thanks!
Thanks for this.
Thnx for uploading all of ur videos are like diamond to me..thnx it helped a lot
@5:16 Whif the vertex has more than one edge coming outta it? well, the graph disconnects, but proving THAT complicates things.
better unleash Euler's Bazooka (v-e+r=2, with r=1). giving the desired answer.
I mean, what's the use of developing Euler's Bazooka (moar like Euler's Panzerfaust, amirite) if you don't use it?
3:01 Do you mean cycle? Or is loop = cycle in your terminology?
Show by means of an example that a simple diagraph in which exactly one node has indegree 0 and every other node has indegree 1 is not necessary a directed tree?
Hey man, what if you delete a vertex with a degree of 2? Doesn't that throw the proof of e=v-1 out of whack? Thanks
But then you would have an isolated vertex below it (the deleted vertex's daughter) and thus it would no longer be a single tree.
Of course, thanks for your reply!
@@Trevtutor That's true, but you glossed over that a bit. The proof didn't seem very robust as a result, IMO. I realize that you have limited time in a video when you're trying to cover material, but just trying to throw out some (hopefully) constructive criticism.
I am having difficulty with the proof by induction. The basis step talks about |e|=0. and then you show that if the property already holds for some tree, then it'll hold for a **smaller** tree. But this is not the same as the "k+1" step. for this proof to be complete, don't you need to start from the largest possible tree instead of the smallest possible tree?
You show that it holds for the smallest possible tree (e=0), then for some arbitrary e=k+1, you show that it can be broken down into components e
Thanks!
I am still a bit confused as to what is going on around time 6:05. The way I understand it, is that you apply the induction hypothesis to the bigger tree (using e'+1), and from that, you show about e'.
by the way, my I ask which tools you're using to produce these beautiful videos? software? devices?
@@tryingtolearn2966 Really, it's just that if you assume the tree you're working with is consistent with e = v - 1, then by removing an edge, the resulting tree also seems to show the same properties. All you need to do is prove that this resulting tree actually does follow the hypothesis, and to prove that, you just need to remove an edge from it and prove that the next tree also follows it. Eventually, you'll stumble upon the base case tree that has already been proven to have the wanted consistency, which creates a chain reaction. Remember, all trees start out with 1 vertice. By adding an edge, you must also add a vertice that it will connect to, keeping the degrees of each individual vertice = 1.
How many different directed trees are there with three nodes ????
which software is this in you video????
man i got an A thanks man for yr help
Trees shred!!!
all you need is tree(positive space/nursery).
great
Tree chapter please
Is it that I am stupid? I can’t understand
So so