It's all you! I just do my best to help! Thanks for watching and be sure to check out my Graph Theory playlist for more: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html More videos are coming on graph theory and discrete math in general. Let me know if you ever have any requests!
So glad it helped! Thanks for watching and you may be interested in this new lesson that just came out about simple bounds on vertex connectivity: th-cam.com/video/JUrO0sAGSYg/w-d-xo.html
Always appreciate your videos! I think the k-connectedness has been the least intuitive of all of the graph theory definitions so far, but I'm sure I'll understand at some future point in time, why it is useful to exists as an idea.
Awsome explanation. What is the lower and upper bound for vertex connectivity k(G) of a directed graph? since all provided examples are based on undirected graphs. Thanks
Thank you, Shima! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Let me know if you ever have any questions!
@@WrathofMath I have a test tomorrow and I was super confused and watching your video made it crystal clear. Please continue the great work, and I hope your channel becomes super famous :) :)
My pleasure, thanks for watching! If you’re looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
In the video you said that for a complete graph with n vertices the vertex connectivity is n-1 by doing so we are left with a single vertex and by convection a single vertex is always connected. Correct me if i am wrong
Thanks for the video, and i wonder whether the following is true : ( Does every 3-connected graph has connectivity 3 ? ) , Hope to hear from you as soon as you can.
Thanks for watching and for your question! The best lower and upper bound that come to my mind immediately, that hold for any regular graph, are as follows. The lower bound is 0. A graph can be r-regular for any number r and still be disconnected. Consider the union of two K5 graphs. That graph is 4-regular and disconnected. If G is r-regular, we can say r is an upper bound on the vertex connectivity. This has nothing in particular to do with the graph being r-regular however. In any graph, we can say its minimum degree is an upper bound on its vertex connectivity, because if we consider a vertex v of minimum degree, we could delete all of v's neighbors to isolate v, thus disconnecting it from the rest of the graph (or making the graph trivial, which also counts). In the case of an r-regular graph, r just happens to be the minimum degree, so r is our upper bound. Does that help?
Thanks for watching and you could probably produce an argument based on congruence mod 5, having to do with the 5-cycles in the graph, though I can't say I have seen that done. Play around with deleting vertices of the graph a little bit and you should be able to find the vertex connectivity without too much trouble. Remember you need to find a number of vertices that can be deleted to disconnect it, and then establish that the graph cannot be disconnected by deleting fewer than that number! The Petersen graph is vertex transitive, which makes this process a bit simpler.
What does it mean for a graph to be 0-connected? Does it mean the same as "disconnected"? If so, then this causes a contradiction. For example, in the book A First Course in Graph Theory pg. 116 it says that a "k-connected graph is also L-connected for every integer L with 0
Thanks for watching and good question. Like being k-connected for any fixed integer k, it is not necessarily the maximum. If I say a graph is 2-connected, that does not mean it isn't also k-connected for some k greater than 2. So every graph is 0-connected, which is why it's a somewhat useless thing to mention. If a graph happens to be k-connected for ONLY k=0, then indeed it is disconnected, but every graph is 0-connected.
Thanks for the request! I will try do a lesson on that soon. Here is a general hint/guideline on how to prove it. First, take care of disconnected and trivial graphs, then take care of complete graphs with at least 2 vertices (complete graphs with just 1 vertex are trivial graphs). Those two things are fairly straightforward. Then we only have to consider connected non-complete graphs, G, with at least 3 vertices. Such graphs have a minimum degree less than or equal to n-2 since they aren't complete. Show that the edge connectivity must be less than or equal to this minimum degree (just imagine deleting all the edge incident to a vertex of min degree). Then consider a minimum edge cut X (which we now know has cardinality less than or equal to n-2) and notice that G-X must have two components, say G1 and G2. Consider 2 cases. Case 1 is that every vertex of G1 was adjacent to every vertex in G2 in the original graph G. Considering the number of edges X must have in this event, and working with some inequalities, will produce a contradiction, so in fact this case cannot occur. Case 2 is that G1 has a vertex, say u, not adjacent to a vertex, say v, in G2. Then we should be able to disconnect G by deleting vertices incident with edges of X, and since deleting a vertex will delete its incident edges, we'll have to delete at MOST |X| vertices, hence the vertex connectivity is less than |X| which is the edge connectivity. That is just a rough outline!
Good morning, my math savior Can you explain how this must be done, To show that graph G of order 𝑛 ≥ 𝑘 + 1 is k-connected, it suffices to verify that 𝐺 − 𝑆 is connected for every set 𝑆 ⊆ 𝑉(𝐺) with |𝑆| = 𝑘 − 1.
Thank you for your support and let me just clarify to be sure what you're asking! Are you asking how to prove that statement is true? As in, how to prove that: if G is a graph of order n (at least k+1) and G-S is connected for every 𝑆 ⊆ 𝑉(𝐺) with |𝑆| = 𝑘 − 1 then G is k-connected?
Great work. You are literally pulling me through this discrete math course one video at a time.
It's all you! I just do my best to help! Thanks for watching and be sure to check out my Graph Theory playlist for more: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
More videos are coming on graph theory and discrete math in general. Let me know if you ever have any requests!
Out of curiosity, how'd the rest of your discrete math course go?
this is so much better than reading a million slides
So glad it helped! Thanks for watching and you may be interested in this new lesson that just came out about simple bounds on vertex connectivity: th-cam.com/video/JUrO0sAGSYg/w-d-xo.html
Best graph theory videos on TH-cam 🙌
Glad I stumbled across your content, not only are you a good teacher the video quality is very refreshing compared to other discrete math youtubers.
Always appreciate your videos! I think the k-connectedness has been the least intuitive of all of the graph theory definitions so far, but I'm sure I'll understand at some future point in time, why it is useful to exists as an idea.
Very useful content, thx bro!
Awsome explanation. What is the lower and upper bound for vertex connectivity k(G) of a directed graph? since all provided examples are based on undirected graphs. Thanks
Thank you so muchh, a savior indeed
You're very welcome, so glad it helped! Let me know if you ever have any questions!
Very beautiful teaching! 🙏
Thank you, Shima! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Let me know if you ever have any questions!
Thank you 🙏
You are amazing, thank you SO MUCH!!
My pleasure! Thanks for watching!
@@WrathofMath I have a test tomorrow and I was super confused and watching your video made it crystal clear. Please continue the great work, and I hope your channel becomes super famous :) :)
thank you sir
OMG, this looks so simple after your video
Glad to hear it! Thanks for watching and let me know if you ever have any questions!
@@WrathofMath Please I have a questions : What's a trivial walk Is it an isolated vetex ?
Thank you very much sir
My pleasure, thanks for watching! If you’re looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
can you recommend for me a book which contain some examples, exercises & solutions please !
In the video you said that for a complete graph with n vertices the vertex connectivity is n-1 by doing so we are left with a single vertex and by convection a single vertex is always connected. Correct me if i am wrong
Thanks for the video, and i wonder whether the following is true : ( Does every 3-connected graph has connectivity 3 ? ) , Hope to hear from you as soon as you can.
thank you soooo much
My pleasure! Thanks a lot for watching and let me know if you ever have any video requests!
excellent
Thank you!
Good day sir, what is the lower and upper bound for vertex connectivity k(G) of a regular graph
Thanks for watching and for your question! The best lower and upper bound that come to my mind immediately, that hold for any regular graph, are as follows.
The lower bound is 0. A graph can be r-regular for any number r and still be disconnected. Consider the union of two K5 graphs. That graph is 4-regular and disconnected.
If G is r-regular, we can say r is an upper bound on the vertex connectivity. This has nothing in particular to do with the graph being r-regular however. In any graph, we can say its minimum degree is an upper bound on its vertex connectivity, because if we consider a vertex v of minimum degree, we could delete all of v's neighbors to isolate v, thus disconnecting it from the rest of the graph (or making the graph trivial, which also counts). In the case of an r-regular graph, r just happens to be the minimum degree, so r is our upper bound.
Does that help?
@@WrathofMath thank you very much sir, well appreciated
Whoa, you've got more cuts than a DJ!
Superb And AmaZiNg
Thanks sir!!
Thanks so much for watching and you're very welcome!
@@WrathofMath thanku
What is the vertex connectivity of a Peterson graph? Is it related to modulo 5 ?
Thanks for watching and you could probably produce an argument based on congruence mod 5, having to do with the 5-cycles in the graph, though I can't say I have seen that done. Play around with deleting vertices of the graph a little bit and you should be able to find the vertex connectivity without too much trouble. Remember you need to find a number of vertices that can be deleted to disconnect it, and then establish that the graph cannot be disconnected by deleting fewer than that number! The Petersen graph is vertex transitive, which makes this process a bit simpler.
Can I say K-connected = vertex connectivity - 1?
OMG :(((( thank you so muchhhhhh
What does it mean for a graph to be 0-connected? Does it mean the same as "disconnected"? If so, then this causes a contradiction.
For example, in the book A First Course in Graph Theory pg. 116 it says that a "k-connected graph is also L-connected for every integer L with 0
Thanks for watching and good question. Like being k-connected for any fixed integer k, it is not necessarily the maximum. If I say a graph is 2-connected, that does not mean it isn't also k-connected for some k greater than 2. So every graph is 0-connected, which is why it's a somewhat useless thing to mention. If a graph happens to be k-connected for ONLY k=0, then indeed it is disconnected, but every graph is 0-connected.
@@WrathofMath Great explanation it's all clear now. Thanks Sean!
Please give a example of k(G)=3
complete graph with 4 vertices works
Could really use the help proving this:
every Hamiltonian-connected graph of order 4 or more is
3-connected
Why we use k(G) >= k
Please provide the proof for vertex connectivity is less than egde connectivity.
Thanks for the request! I will try do a lesson on that soon. Here is a general hint/guideline on how to prove it. First, take care of disconnected and trivial graphs, then take care of complete graphs with at least 2 vertices (complete graphs with just 1 vertex are trivial graphs). Those two things are fairly straightforward.
Then we only have to consider connected non-complete graphs, G, with at least 3 vertices. Such graphs have a minimum degree less than or equal to n-2 since they aren't complete. Show that the edge connectivity must be less than or equal to this minimum degree (just imagine deleting all the edge incident to a vertex of min degree). Then consider a minimum edge cut X (which we now know has cardinality less than or equal to n-2) and notice that G-X must have two components, say G1 and G2. Consider 2 cases. Case 1 is that every vertex of G1 was adjacent to every vertex in G2 in the original graph G. Considering the number of edges X must have in this event, and working with some inequalities, will produce a contradiction, so in fact this case cannot occur.
Case 2 is that G1 has a vertex, say u, not adjacent to a vertex, say v, in G2. Then we should be able to disconnect G by deleting vertices incident with edges of X, and since deleting a vertex will delete its incident edges, we'll have to delete at MOST |X| vertices, hence the vertex connectivity is less than |X| which is the edge connectivity. That is just a rough outline!
GOD
Notability?
Yessir!
Good morning, my math savior
Can you explain how this must be done,
To show that graph G of order 𝑛 ≥ 𝑘 + 1 is k-connected, it suffices to verify that 𝐺 − 𝑆 is
connected for every set 𝑆 ⊆ 𝑉(𝐺) with |𝑆| = 𝑘 − 1.
Thank you for your support and let me just clarify to be sure what you're asking! Are you asking how to prove that statement is true? As in, how to prove that: if G is a graph of order n (at least k+1) and G-S is connected for every 𝑆 ⊆ 𝑉(𝐺) with |𝑆| = 𝑘 − 1 then G is k-connected?
@@WrathofMath yes Sir