Proof: A Bridge is the Unique Path connecting its End Vertices | Graph Theory
ฝัง
- เผยแพร่เมื่อ 26 ก.ค. 2020
- If e=uv is a bridge of a graph, then there exists a unique path connecting u and v, and this path is the bridge itself! We'll be proving this result about bridges and their end vertices in today's graph theory lesson!
Recall that a bridge of a connected graph is an edge that when deleted disconnects the graph. We can also say that a bridge of a disconnected graph is an edge that, when deleted, disconnects the component it belongs to. The result we prove today tells us that not only is a graph disconnected when a bridge is removed, but in particular - the end vertices of the bridge become disconnected.
Proof that a walk implies a path: • Proof: If There is a u...
Lesson on bridges: • What are Bridges of Gr...
◆ 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
Underrated video, this was one of the hardest proofs I had encountered which was not explained well in the book I have :) Thanks!!
Thanks for showing us the path forward 😎
Consider a tree T with n vertices, where n is an odd integer greater than or equal to 3. Let v be a vertex of T. Prove that there exists a vertex u in T such that the distance between u and v is at most (n-1)/2.