Proof: Connected Graph Contains Two Non-Cut Vertices | Graph Theory, Connected Graphs
ฝัง
- เผยแพร่เมื่อ 11 ก.ค. 2024
- Every connected graph with at least two vertices contains two vertices (at least), that can be deleted without disconnecting the graph. Let's say our graph with at least two vertices is G. So there must be two vertices, say u and v, such that G-u and G-v are both connected. Thus, G contains at least two vertices that are not cut vertices. We will prove this theorem in today's video graph theory lesson!
This fun proof uses distance between vertices, geodiscs, and graph diameter! A big bundle of fun to make a pretty nifty proof. We will show that the two end vertices of a longest geodisc in the graph will have the characteristic we want using contradiction. We will assume G-u is in fact disconnected, and show that cannot be true. The same argument would work with G-v if it were disconnected.
This gives us a necessary condition for a graph to be connected. In fact, for graphs with at least 3 vertices, it is also sufficient. We will prove the converse in another lesson!
The argument we make for contradiction, that u cannot lie on either geodisc we introduce, relies on the result that any subpath of a geodisc is also a geodisc. This is easily proven by contradiction (if it were not the case, the whole geodisc would not be a geodisc because it could be shortened by replacing the non-geodisc subpath with an actual geodisc).
Proof that a walk implies a path: • Proof: If There is a u...
Lesson on distance between vertices, which also covers geodiscs and diameter: • Distance Between Two V...
If you're taking a course in Graph Theory, or preparing to, you may be interested in the textbook that introduced me to Graph Theory: “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing extra, and helps me continue to work on Wrath of Math!
PURCHASE "A First Course in Graph Theory": amzn.to/31hgvvJ
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic
I'd never heard it called "geodisc" before coming across your videos, but I kind of like that term now because you can say it a bit faster. In any case, thanks for walking us through this proof!
Great video. If the statement was altered to say |V(G)| >= 3 and G has at least 3 non-cut vertices v where G-v is connected, unless G is a path, how would you approach the proof?
You're great bro. I am really struggling with Graph Theory proofs so it helped me a lott. Thanks a ton :)
Thank you, so glad to help! If you're looking for more graph theory, check out my playlist: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
An elegant proof, as usual. You're great.
Thank you!
Very well explained,i was really struggling with this particular proof
So glad it helped, thanks for watching! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
And let me know if you ever have any lesson requests!
Good Job ,I loved it
Thanks for watching, I'm glad you liked it!
So G-u is the graph that results when you delete the vertex u, and G-v s the graph that results when you delete the vertex v? if so, do we also delete the edges that branch out from u and v? I'm confused because you seem to use a "minus sign" to subtract a vertex from a graph, but you also use a "minus sign" to denote a path between vertices.
Correct. When we delete a vertex, any edge which was incident to it must also be deleted. When the minus sign denotes a path between vertices it should be clear from context. We cannot have a G-v path connecting a graph to a vertex, that is not something that makes sense, so G-v certainly refers to the graph G without v or its incident edges. Similarly, u-v certainly doesn't refer to the graph u without the vertex v, because u is not a graph.
g its a graft u its a vertex how is posible g - u? there are no begin at g could beguin any where? . graft minus 1 vertex because it can not be a path or something like that. there are no initial vertex.
How to proceed plz upload vdo
What if d(u, v) is not the diameter of G, is this statement still hold true???
the diameter of G always exists for a graph with over two vortexes. so it can always be used as an example of why the statement is true.
show that a connected graph which is not a block has atleast two blocks that each contain exactly one cut vertex