QUICK DISCLAIMER: At 7:00 I say "We say a graph is k-connected if we need to delete at least k vertices to disconnect it". This is correct, but misleading. I should have said "We say a graph is k-connected if deleting fewer than k vertices will not disconnect it". The point I want to make is that a graph being k-connected DOES NOT mean that there is a set of k vertices we can delete to disconnect it. It just means we cannot disconnect it by deleting fewer than k vertices. Then, the maximum k for which a graph is k-connected is called the graph's connectivity. For this max value of k, there are k vertices we can delete to disconnect the graph. For clarity, if we need to delete a minimum of 4 vertices to disconnect a graph G, then the graph G has connectivity 4 and is 4-conneced. But it is also 3-connected, 2-connected, 1-connected, and 0-connected. Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions! th-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin Graph Theory course: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Graph Theory exercises: th-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
@@zactranah7942 G is not 3-connected simply because there exists a vertex in G with degree 2. Deleting its two adjacent vertices disconnects it from the graph. So G can indeed be disconnected via deleting only 2 (< 3) vertices.
0:27 Example 1 1:30 2 non-adjacent vertices 2:38 Proof 2:47 Example 2 3 separations needed for isolation Therefore, 3 internally disjointed paths 8:21 Given any 2 non-adjacent vertices means at least 2 internally disjoint paths
Glad to hear it, thanks for watching and if you're looking for more graph theory check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
My pleasure, thanks a lot for watching! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
You're very welcome, thanks for watching! I'm not very familiar with T-joins and matroids, so unfortunately lessons on them will have to wait until I get around to studying them further! I appreciate the request!
My pleasure! Thanks for watching and if you're looking for more graph theory, check out my Graph Theory playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thanks so much for watching, Avi! You've got at least one comment I haven't had the time to respond to yet, something to do with Menger's theorem. I'll take another look when I get a chance! :)
@@WrathofMath Thank you for your response. I have a question would i think would make for a great video ( in relation to this video). Suppose that in the graph G = (V, E) there are two vertex sets V1, V2 ⊆ V such that |V1 ∩ V2| > 1 and such that the induced subgraphs G[Vi ] are 2 -connected for i = 1, 2 . Show that G[V1 ∪ V2] is 2 -connected.
QUICK DISCLAIMER: At 7:00 I say "We say a graph is k-connected if we need to delete at least k vertices to disconnect it". This is correct, but misleading. I should have said "We say a graph is k-connected if deleting fewer than k vertices will not disconnect it". The point I want to make is that a graph being k-connected DOES NOT mean that there is a set of k vertices we can delete to disconnect it. It just means we cannot disconnect it by deleting fewer than k vertices. Then, the maximum k for which a graph is k-connected is called the graph's connectivity. For this max value of k, there are k vertices we can delete to disconnect the graph.
For clarity, if we need to delete a minimum of 4 vertices to disconnect a graph G, then the graph G has connectivity 4 and is 4-conneced. But it is also 3-connected, 2-connected, 1-connected, and 0-connected.
Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
th-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: th-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
isn't the graph G shown in your video 3-connected? Could you explain why it is just 2? Thanks!
@@zactranah7942 G is not 3-connected simply because there exists a vertex in G with degree 2. Deleting its two adjacent vertices disconnects it from the graph. So G can indeed be disconnected via deleting only 2 (< 3) vertices.
All your graph videos have been very helpful!
I´ve wacthed them all for my graph theory course.
Thank you, Juan, I'm very glad to hear that! I hope you've enjoyed your course and let me know if you ever have any video requests!
I agree with Juan, your videos have been really helpful! I enjoy these videos very much. Keep making them!
How'd the rest of your graph theory course go?
0:27 Example 1
1:30 2 non-adjacent vertices
2:38 Proof
2:47 Example 2
3 separations needed for isolation
Therefore, 3 internally disjointed paths
8:21 Given any 2 non-adjacent vertices means at least 2 internally disjoint paths
Really enjoyed the exposition. Thanks!
My pleasure, thanks for watching!
Any plans for Konig's theorem?
Thank you so much this video is very helpful!
Glad to hear it, thanks for watching and if you're looking for more graph theory check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
dude, can ya name the software you are using for this presentation.
Great lesson, now I get it. Thankyou so much for the help :)
My pleasure, thanks a lot for watching! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Pretty clear!
Is there any algorithm that implements this ?
Great video! Thank you so much!
My pleasure, thanks for watching!
Thank u so much sir ur way of teaching z really great
You're very welcome and thank you!
amazing teaching
Thank you, Laiq! If you're looking for more graph theory, check out my playlist! th-cam.com/video/ZQY4IfEcGvM/w-d-xo.html
@@WrathofMath Okay I watch regularly because my research field is spectral graph theory
Thank you so much for these awesome videos! Could you please cover T-joins and Matroids please
You're very welcome, thanks for watching! I'm not very familiar with T-joins and matroids, so unfortunately lessons on them will have to wait until I get around to studying them further! I appreciate the request!
nice explaination,thank you!!!!!!
My pleasure! Thanks for watching and if you're looking for more graph theory, check out my Graph Theory playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Menger? More like "Banger", just like all the rest of your graph theory videos 👍
amazing!
Thank you! Glad it helped and check out my Graph Theory playlist if you're looking for more: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
LEGEND
It's my duty!
I appretiate you
I appreciate you watching! Let me know if you ever have any questions!
Isn't it 3-connected (not 2-connected), because you need to remove at least 3 vertex to make it disconnected?
Hello, you may have missed the bottom right vertex, where if the two adjacent vertices are removed, then the graph becomes disconnected.
Love you
Thanks so much for watching, Avi! You've got at least one comment I haven't had the time to respond to yet, something to do with Menger's theorem. I'll take another look when I get a chance! :)
@@WrathofMath Thank you for your response. I have a question would i think would make for a great video ( in relation to this video).
Suppose that in the graph G = (V, E)
there are two vertex sets V1, V2 ⊆ V such that |V1 ∩ V2| > 1 and such that the induced
subgraphs G[Vi
] are 2 -connected for i = 1, 2 . Show that G[V1 ∪ V2] is 2 -connected.
dude, can ya name the software you are using for this presentation.
Thanks for watching, and sure thing - it's Notability on iPad Pro.