Proof: Every Connected Graph has a Spanning Tree | Graph Theory
ฝัง
- เผยแพร่เมื่อ 5 ต.ค. 2020
- Every connected graph has a spanning tree - this means that every connected graph G contains a subgraph H with three properties. H is connected, has no cycles, and has all vertices of G. A connected graph with no cycles is a tree. A subgraph of G with all vertices of G is called a spanning subgraph. Thus, a connected spanning subgraph with no cycles is a spanning tree! We'll be proving this useful result in today's graph theory video lesson!
Intro Tree Graphs: • Intro to Tree Graphs |...
Spanning Subgraphs: • What is a Spanning Sub...
Edge is a Bridge iff it Lies on No Cycles: • Proof: An Edge is a Br...
◆ Donate on PayPal: www.paypal.me/wrathofmath
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic
![[TH] VCT Pacific Stage 2 - Week 4 Day 1 // PRX vs RRQ | GE vs GEN](http://i.ytimg.com/vi/iIi2_04jGr0/mqdefault.jpg)
The costume makes it feel like I'm receiving arcane knowledge.
This is my first time coming across your channel. I really love this idea! It's nice seeing high quality content on topics outside the usual high school / first year maths curriculum.
Thank you! My new videos are higher quality but not so decorative haha, I haven't had time for the halloween decor since this one year I did it - but hopefully I will have time to decorate again soon!
Maaaan i will be so happy when i see your channel maybe 2 years from now when you finally get mainstream and blow up knowing that i was here since the beginning :3
Great videos, keep it up, proud of you!
Really appreciate it! If you wanna help me grow, sharing the videos is the best way! And if you haven't seen the new episodes of MathBits, I hope you'll check them out! 😊th-cam.com/video/gbwbAzhXQ5k/w-d-xo.html
Man your channel is so good! Makes it entertaining to study math
Thanks so much! So glad you're enjoying the lessons, plenty more to come! I was debating whether or not to break out the Halloween set and Christmas set for my math lessons this Holiday season. I'm still not sure, but I'd like to if I have the time!
Sir due to ur awesome and detailed classes on advanced graph theory i scored very good marks and I will have a good opportunities in mathematics
Thanku for u support by doing videos keep going and u will get diamond youtube plate for sure
Thank u......
So glad to hear you scored well and my lessons were helpful! It's your hard work paying off, great job and let me know if you ever have any video requests!
Every connected graph? More like "Amazing lectures that can also make you laugh!" 😆
It’s almost like recursion, because we can then apply this onto G-e until the subgraph has no cycles, and then we obtain our spanning tree.
So essentially we don’t have to show these other steps, because we have an arbitrary number of edges m+1, and looking at the graph of m gives us either
A.) A graph which is connected and acyclic (A MST, result)
or B.) A graph which is connected and has a cycle. And Because it’s connected, we can use the recursive formula again (but here we say that because it’s connected, we can use the inductive hypothesis to claim that there is an MST present on this subgraph and hence the graph G)
this is so awesome I love this theme, more educational people should take this type of approach is genuinely really engaging
Thank you! I made all my lessons very spooky in October that year, I hope I'll have time to do that again some day!
Does this proof hold for A graph is connected if and only if
it contains a
spanning tree .?
loved the video btw!😊
Thanks for trying to make it fun, snaps me out of the doom loop a bit.
06:06 indeed it's clear since a cycle provides two paths to any vertex on it
BTW nice job
Precisely! And thank you!
In grad school, I developed a few theorems about mathematicians, and constantly, I am proven completely correct -- and always in the best ways. I love my people
Thanks for watching! And did you mean "theorems about mathematicians"? Or did you mean to type "theorems about mathematics"?
@@WrathofMath yes, he most likely did
So creative 💯
Please explain the proof of Brooks theorem.
can you make a video about clique cover????
Thanks for watching and great idea! I'll add it to my list. I have been away from the studio for over a week now, but will be returning home soon - and will begin recording more of the great requests I've received!
My professor says induction in graph theory trips up a lot of students, since it's kind of weird (spooky, even). Usually for the inductive step, students will assume it's true for a n-1 graph, then add a vertex/edge to get the n graph back. The problem is that you may not get every n graph back just by adding a random vertex/edge back. Therefore the only way to make sure you've proven it for every n graph is to start with an n graph, subtract a vertex/edge and take inductive step, then add it back to get the original graph. Jeepers!
Haha, it is a very nifty proof technique, spooky may be accurate! Yeah that's a key detail to not get messed up! The induction hypothesis has to concern the object you're trying to prove something about, for n rather than n-1. And so the real movement is usually going from n to n-1, showing n-1 satisfies the condition to apply the induction hypothesis, like still being connected or still being a tree, and then adding in that extra edge again and proving that n works too! It's amazing how slick that process often is.
Could you explain how did you use induction hypothesis? It's confusing for me.
Thanks for watching and sure thing! Remember that our induction hypothesis is to assume that all connected graphs with m edges have a spanning tree, for some positive integer m. We know it is true for m=1, so this is perfectly reasonable. Then, in the induction step we consider a graph G with m+1 edges that is not a tree (because if it is a tree then it is its own spanning tree and we have nothing to prove). We delete an edge, e, from a cycle of G, to get G-e with m edges, AND this new graph also has to be connected because deleting an edge from a cycle never disconnects a graph. That is why we can use our induction hypothesis to assume it has a spanning tree. Since we didn't delete any vertices, this spanning tree of G-e also spans the original graph G. Here is a proof of the deleting an edge from a cycle result: th-cam.com/video/lST8mLny9pk/w-d-xo.html
Hope that helps!
@@WrathofMath Thanks a lot!!
Very nice videos. I'll recommend them to my friends too. You saved me before my exam. I really appreciate this. Thanks again.
@@WrathofMath do you mean we know this is true for m=0 and not m=1?
How about m=2?
YOU RE GOOD!
Thank you!
Too spoopy for me! The math was comforting tho
You were probably more comfortable than me in that darn costume! 😂
where is the removing an edge from a cycle of a connected graph wont result in a disconnected graph proof
Why did u wear it?
He wears it because YOU ARE FOOT
monster
I am looking pretty spooky in this one!
.
Whts about dress
It was my Halloween costume! For all of October last year, I wore this ridiculous costume and made my lessons spooky!
Sir your class is sooo good...but your costume makes mine focus fall in ur face
Thank you Nahla, I understand these Halloween videos can be a little distracting haha, but it was only one month that I made them like this, so not many of my graph theory videos are like this, only 5 or something out of more than 150! Let me know if you ever have any video requests!
😍😍😍😍
Thanks for watching!
is really this much talking required in a proof
The rhetoric of a proof depends on its context. Is it in a textbook? A peer-reviewed publication? A lecture? On a napkin over a cup of coffee? This seems like a well-constructed member of the family of educational whiteboard proofs in my opinion. Check out '99 variations on a proof' by Philip ording; it may enrich your concept of mathematical proof!