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! ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
I'm attending a course of Data Mining in which we are talking about CHAMELEON Algorithm (clustering). Your video deals with precisely those concepts that are the basis of the algorithm. Thanks
A nontrivial graph G is k-edge-connected if and only if there exists no nonempty proper subset W of V (G) such that the number of edges joining W and V (G) - W is less than k. Can you explain about this theorem. Im having a hard time on it.pleaase😪
Thanks for watching and good question! I'll do a lesson on that as soon as I can, but I thought about it a little bit and here are some hints/suggestions you may find helpful. To prove that being k-edge connected implies no nonempty proper subset W of V (G) such that the number of edges joining W and V (G) - W is less than k, I recommend using contradiction, I think that takes care of things pretty quickly. To prove that no nonempty proper subset W of V (G) such that the number of edges joining W and V (G) - W is less than k implies that a graph is k-edge connected, I recommend using contrapositive. Extra hint: if a graph is not k-edge connected, you're guaranteed an edge cut with fewer than k edges. Might as well take a minimum edge cut to keep things simple, and then use that to cut your graph into two parts. Minimum edge cuts can only ever cut a connected graph into two components.
I love your channel so much. If it’s no that difficult, could you please explain how to prove this theorem: If every vertex of a planar graph has even degree, it is 2-colorable?
Thanks a lot, I appreciate that! Perhaps you misread or accidentally mis-stated the theorem in question because that statement is not true. For example, consider the 3-cycle! It is planar, is 2-regular, and requires 3 colors!
Wrath of Math I found this proof which I don’t fully understand: Consider the dual G' of the given graph G. Since every vertex of G has even degree, every face of G' has an even number of edges. By coloring any vertex and then alternating the colors, we can 2-color the vertices of G', and this coloring corresponds to a 2-coloring of the faces of G. I
Oh, so in the original question you were talking about a 2-coloring of the FACES of G, not the vertices of G! My bad, I'll take a closer look and see if I can do a video on it or explain it here in the comments.
@@WrathofMath also, I would be very grateful if you could explain how to prove this: In graph G any trial connecting vertices a and b contains more than 2 edges. Prove that in the complement of graph G, for any two vertices, there is a trial containing at most THREE edges
Thanks for watching and for the question, you are right depending precisely on what you mean. The minimum edge cut of a disconnected graph is the empty set { }, not the number 0. Since the empty set has 0 elements and is a minimum edge cut of any disconnected graph, the edge connectivity of a disconnected graph is 0.
I would like to request a video on different graph product operations including the cartesian product, conormal product, lexicographical product, normal product, rooted product, and tensor product.
Thanks for watching and the ideas, those would be fun and there are some graph product lessons I have begun planning, but it will take some time to get to all of them!
@@WrathofMath Mathematica 13.1 and the Wolfram language will include a graph product function for this and I want to use it but before I use the new function GraphProduct I want to understand what the function will do.
Well explained teacher ! I was just wondering about another possibility of cutting the graphe with fewer edges cut than Y For example let it be Z ={e7} I think It's minimum and enough to cut the graphe Is it correct sir? 🤔
Thanks for watching and for the question! In G, {e7} is not an edge cut. If we remove e7, we're left with a cycle on 6 edges, which is certainly connected. Remember when we remove edges, we do not remove their incident vertices. This is in contrast to deleting vertices, where do remove the incident edges (this is because an edge is defined by its end vertices, so without the vertex there can be no edge). Hope that helps, and if you're looking for more graph theory - check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Hi Keith, thanks for watching! What sort of math are you doing now? I'd be happy to do some lessons on a specific topic if you have one, or a few, in mind!
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!
ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin
Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
Again came back after watching your class on 'Matching', definitely you are a gem of a teacher.
I'm attending a course of Data Mining in which we are talking about CHAMELEON Algorithm (clustering). Your video deals with precisely those concepts that are the basis of the algorithm. Thanks
So glad they have been helpful, thank you for watching!
Helped me so much to understand things I did in lectures. Thanks!
perfect explanation, talented at teaching definitely.
Thanks so much! I am glad it helped and let me know if you ever have any video requests!
Great explanation
Thank you!
I am reporting this topic tomorrow, thank you 😇😁
Hi
any graph that doesn't have edge connectivity?
Can you answer?
A nontrivial graph G is k-edge-connected if and only if there
exists no nonempty proper subset W of V (G) such that the number of edges
joining W and V (G) - W is less than k.
Can you explain about this theorem. Im having a hard time on it.pleaase😪
Thanks for watching and good question! I'll do a lesson on that as soon as I can, but I thought about it a little bit and here are some hints/suggestions you may find helpful.
To prove that being k-edge connected implies no nonempty proper subset W of V (G) such that the number of edges joining W and V (G) - W is less than k, I recommend using contradiction, I think that takes care of things pretty quickly.
To prove that no nonempty proper subset W of V (G) such that the number of edges joining W and V (G) - W is less than k implies that a graph is k-edge connected, I recommend using contrapositive. Extra hint: if a graph is not k-edge connected, you're guaranteed an edge cut with fewer than k edges. Might as well take a minimum edge cut to keep things simple, and then use that to cut your graph into two parts. Minimum edge cuts can only ever cut a connected graph into two components.
@@WrathofMath Wow, you are so very reliable sir, Thank you so much. I will recommend this channel to my classmates. Lovelots.
Thank you sir 😍😍
My pleasure, thanks for watching!
I love your channel so much. If it’s no that difficult, could you please explain how to prove this theorem:
If every vertex
of a planar graph has even degree, it is 2-colorable?
Thanks a lot, I appreciate that! Perhaps you misread or accidentally mis-stated the theorem in question because that statement is not true. For example, consider the 3-cycle! It is planar, is 2-regular, and requires 3 colors!
Wrath of Math I found this proof which I don’t fully understand:
Consider the dual G' of the given graph G. Since every vertex of G
has even degree, every face of G' has an even number of edges. By
coloring any vertex and then alternating the colors, we can 2-color
the vertices of G', and this coloring corresponds to a 2-coloring of
the faces of G.
I
Oh, so in the original question you were talking about a 2-coloring of the FACES of G, not the vertices of G! My bad, I'll take a closer look and see if I can do a video on it or explain it here in the comments.
@@WrathofMath also, I would be very grateful if you could explain how to prove this:
In graph G any trial connecting vertices a and b contains more than 2 edges. Prove that in the complement of graph G, for any two vertices, there is a trial containing at most THREE edges
Wrath of Math how are things going? Have you managed to prove this theorem?
Good day sir, what is the minimum edge cut of a disconnected graph? Is it 0?
Thanks for watching and for the question, you are right depending precisely on what you mean. The minimum edge cut of a disconnected graph is the empty set { }, not the number 0. Since the empty set has 0 elements and is a minimum edge cut of any disconnected graph, the edge connectivity of a disconnected graph is 0.
@@WrathofMath Good morning sir, from Philippines, Thank you so much for your response, well-appreciated
I would like to request a video on different graph product operations including the cartesian product, conormal product, lexicographical product, normal product, rooted product, and tensor product.
Thanks for watching and the ideas, those would be fun and there are some graph product lessons I have begun planning, but it will take some time to get to all of them!
@@WrathofMath Mathematica 13.1 and the Wolfram language will include a graph product function for this and I want to use it but before I use the new function GraphProduct I want to understand what the function will do.
Wonderful
Thank you, Sashi!
Well explained teacher !
I was just wondering about another possibility of cutting the graphe with fewer edges cut than Y
For example let it be Z ={e7}
I think It's minimum and enough to cut the graphe
Is it correct sir? 🤔
Thanks for watching and for the question! In G, {e7} is not an edge cut. If we remove e7, we're left with a cycle on 6 edges, which is certainly connected. Remember when we remove edges, we do not remove their incident vertices. This is in contrast to deleting vertices, where do remove the incident edges (this is because an edge is defined by its end vertices, so without the vertex there can be no edge). Hope that helps, and if you're looking for more graph theory - check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
upload a video lect relationship of vertax connectivity edge connectivity and min dgree of graph
Thank you so much
Thank you so much for watching!
What's the edge connectivity of the biggest edgelord in the world?
This video was *extremely* edgy!
Hi
I request anything for my age.
:)
Hi Keith, thanks for watching! What sort of math are you doing now? I'd be happy to do some lessons on a specific topic if you have one, or a few, in mind!
@@WrathofMath ratios
Hii