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! ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin Graph Theory course: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Graph Theory exercises: ua-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
Wrath of Math However, if for example graph A has two adjacent edges on the same side, while graph B has only one adjacent edge on one side, are graph A and B isomorphic?
Man... seriously.. Are you a professor? this is what you do in your daily life? Man, anything else you do if a complete waste of time.... this is your stuff. I mean it, exist a lot of person that can comprehend a complex concept, but persons that can comprehend it, digest it and later explain it in a easy and simple way, is a divine gift........
Great explanation, sir! I've an exam on algebra, three days later. No doubt now persists in mind. You must have been a better student, but believe me, you are a great teacher. God bless you. Love from 🇮🇳. One more request, I am an undergraduate student of mathematics, and I want to be a mathematician like you. Can you please suggest me some books of college level?
At 11:41, you have assumed that the distance between d(a,b) = 1 and what follows is that since d(a,b) must be even, it can't be 1. Why have you chosen 1? If would have been if you chose d(a,b) to be 2. How would you proceed then? The assumption fit in perfectly because it then helps us prove that d(a,b) is not even.
Thanks for watching and for your question! The important point is that we didn't exactly assume d(a,b) = 1, what we assumed was that X and Y did not form a bipartite partitioning of V(G) - that was our assumption for the sake of contradiction. We assumed for the sake of contradiction that our partitioning of V(G) was NOT bipartite, and thus there exists a pair of vertices, a and b, that are adjacent and in the same set (X or Y). Thus, d(a,b) MUST be equal to 1 since they are adjacent, there is no other possibility due to our contradiction assumption. Good question, does that help? Here is a lesson I did on distance between vertices in case the precise definition of that is unclear: ua-cam.com/video/ZmakwnZv-qo/v-deo.html
when you talk about distance between 2 nodes, do you mean the shortest distance? Coz there could be multiple paths between nodes and each could be of different lengths.
why you take intersection point if we take without intersection we obtain closed walk wa to ab and bw of odd length which gives odd cycle by leema and which is contradiction...
if a=w, doesn't this mean that we assume that a, b belong to X? Since d(w, w) = 0, so w has to be in X. But, as a result, this contradicts the prior assumption that a, b belong to X or Y, because if both a and b are in the same set and a=w is in X, then we have not covered the case for Y.
Shouldn't |P_2^{-1]Q_2(a)| = |P_2| + |Q_2| -1? As P_2 and Q_2 contain the common vertex x so you can only count it once and a doesnt get counted as it is already counted in P_2??
Yo, thanks for giving me some direction. How did this proof assumed that all graphs without odd cycles can be partitioned into 2 sets of vertices with different parity distance to a given vertex ? This statement is clearly not true for graphs with odd cycle, but what makes it true for graphs without odd cycles? Thanks
Sir wher is converse part it is if and only if condition U only show if a graph has no odd cycle then it is bipartite but what about that is G is bipartite then it has no odd cycle
Thanks for watching! I only included what I think is the much harder part to prove in this video, which was also specifically requested by a viewer, and because of how long the video already is I didn't want to make it any longer. If you'd like, I'd be happy to do a video on the proof of the converse!
I was actually in the mood today to do a video on the converse, so I just recorded it. It will be out Sunday 12:00 am EDT. That's a weird time for people in America like me, but not many Americans are watching at this time of year, so I'm trying to release lessons at a time better for everyone else! Thanks for your support :)
So the v in "v is an element of V(G)" for the set X... is different than the v in "v is an element of of V(G)" for the set Y? I ask because you call them both v, but it seems to me like they can't both be the same vertex...
That is correct, assuming you mean around 7:40, calling them both is acceptable in this context of set builder notation. We could read it as "X is the set containing all vertices v in the graph G such that the distance between v and the vertex w is even." Then we read Y as "the set of all vertices v in G such that the distance between v and w is odd". In each case, v is ranging through all vertices of G that have a particular property in order to create each set. If we actually intended on using v to represent an arbitrary member of X, we would certainly need to use a different letter to represent an arbitrary member of Y.
great explanation can you explain this - In a complete graph with n vertices there are n−1/2 edge-disjoint Hamiltonian cycles if n is an odd number and n≥3.
Thank you for watching! Sure, here is a very informal explanation. A Hamiltonian cycle will contain two edges incident with each vertex (one to get there, and one to leave, so to speak). Each vertex is incident to n-1 edges by definition of a complete graph. Of course, n-1 is even if we assume n is odd. Then, if we take all of the edges incident to a vertex, and give pairs of them to as many Hamiltonian cycles as we can, we would give 2 edges to (n - 1)/2 Hamiltonian cycles. We also know that every other vertex needs to give 2 incident edges to each of these (n - 1)/2 Hamiltonian cycles, and of course we know each other vertex has exactly enough edges for that. When we think of making the cycles as "giving edges", we assure that we have edge-disjoint cycles since once we give two edges to a cycle we cannot give those edges to another cycle. The idea of giving edges also suggests the division, as that is often how division is introduced. If you share n-1 apples with your (n-1)/2 friends, how many apples does each friend get? Of course the answer is 2. In our situation, we are asking, "If you must give away 2 apples to make a friend, and you have n-1 apples, how many friends can you make?" The answer is (n-1)/2. A silly explanation, but I hope it helps some!
Glad it helped, thanks for watching and if you're looking for more graph theory - check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Let me know if you ever have any video requests!
Hmmmm, wouldn't |P_2| = |Q_2|, necessarily (read: stronger claim than P_1 and P_2 having the same parity)? I'm assuming distance d(s, t) is the length of the shortest path between vertices s and t in the connected graph; |P| = d(w, a) and |Q| = d(b, w) are the same parity; |P_1| = |Q_1|; d(a, b) = 1. PS: Awesome video -- thank you for sharing!
Thanks for watching and good question! I mention early in the video that "A graph is bipartite if and only if all of its connected components are bipartite" (let me know if you'd like explanation of that fact). So that is why we only have to consider connected graphs, because if a graph is disconnected then we can just apply our proof to its connected components, proving each component is bipartite and thus the whole disconnected graph is as well. Does that help?
Haha, thanks for watching and good question! I've done a bit of programming, but I am no computer scientist! But us graph theorists benefit a lot by counting from 0 in a lot of situations, particularly when writing out the vertices of a walk! So when I put on my graph theory hat, I count from 0!
Haha, I suppose they kind of do, I have never looked at them that way! If you can find subliminal images of happiness in my math lessons, all the better!
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!
ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: ua-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
Yes, the exact explanation I've been finding to clear up my questions.
Thanks for watching, I am so glad it helped!
Wrath of Math However, if for example graph A has two adjacent edges on the same side, while graph B has only one adjacent edge on one side, are graph A and B isomorphic?
Man... seriously.. Are you a professor? this is what you do in your daily life? Man, anything else you do if a complete waste of time.... this is your stuff. I mean it, exist a lot of person that can comprehend a complex concept, but persons that can comprehend it, digest it and later explain it in a easy and simple way, is a divine gift........
isn't proof over at 13:52 if we say [wab] is closed odd walk hence it should contain odd cycle hence contradiction
Sean your explanations are honestly awesome! These help me form my own conclusions and get to the proof myself! Thank you so much ☺️
Great explanation, sir! I've an exam on algebra, three days later.
No doubt now persists in mind. You must have been a better student, but believe me, you are a great teacher. God bless you.
Love from 🇮🇳.
One more request, I am an undergraduate student of mathematics, and I want to be a mathematician like you. Can you please suggest me some books of college level?
How did your exam go?
This question came up in one of my CS assignments. Thanks
Glad it helped, thanks for watching!
Thanks so much for making this clear! I pray to have professors who can articulate just like you!
Thank you!
@Wrath_of_Math can you please do a series on discontinuous dynamics?
At 11:41, you have assumed that the distance between d(a,b) = 1 and what follows is that since d(a,b) must be even, it can't be 1. Why have you chosen 1? If would have been if you chose d(a,b) to be 2. How would you proceed then?
The assumption fit in perfectly because it then helps us prove that d(a,b) is not even.
Thanks for watching and for your question! The important point is that we didn't exactly assume d(a,b) = 1, what we assumed was that X and Y did not form a bipartite partitioning of V(G) - that was our assumption for the sake of contradiction. We assumed for the sake of contradiction that our partitioning of V(G) was NOT bipartite, and thus there exists a pair of vertices, a and b, that are adjacent and in the same set (X or Y).
Thus, d(a,b) MUST be equal to 1 since they are adjacent, there is no other possibility due to our contradiction assumption. Good question, does that help? Here is a lesson I did on distance between vertices in case the precise definition of that is unclear: ua-cam.com/video/ZmakwnZv-qo/v-deo.html
@@WrathofMath Thank you so much! It makes more sense now.
when you talk about distance between 2 nodes, do you mean the shortest distance? Coz there could be multiple paths between nodes and each could be of different lengths.
No odd cycles? More like "Nice proof that excites us!" 🙏
Very good and elaborate proof man! Thanks
You’re welcome, thanks for watching! I am glad it was clear!
Your videos are very clear and helpful. Thank you! I hope you will make more videos so I can learn from you
Thanks for watching and I'm so glad you find the lessons helpful! I release new lessons every two days! New lesson comes out tomorrow! :)
Thank you! I was struggling so bad with this proof.
Thanks a lot for watching, Fabrizio! I'm so glad the lesson helped clear it up for you! One of my favorite graph theory proofs!
Excellent video, going over this before we cover the proof more thoroughly in friday's lecture! Cheers WOM!
Thanks for watching!
why you take intersection point if we take without intersection we obtain closed walk wa to ab and bw of odd length which gives odd cycle by leema and which is contradiction...
if a=w, doesn't this mean that we assume that a, b belong to X? Since d(w, w) = 0, so w has to be in X. But, as a result, this contradicts the prior assumption that a, b belong to X or Y, because if both a and b are in the same set and a=w is in X, then we have not covered the case for Y.
Loved the explanation, thanks! :D
So glad it helped! Thanks for watching!
Great explanation, fun to watch!
Thank you, I'm glad to hear it!
Shouldn't |P_2^{-1]Q_2(a)| = |P_2| + |Q_2| -1? As P_2 and Q_2 contain the common vertex x so you can only count it once and a doesnt get counted as it is already counted in P_2??
Tanks!! Really good explanation!
You're welcome, I am glad it helped! Let me know if you ever have any questions!
Absolutely brilliant!
Thank you!
Yo, thanks for giving me some direction.
How did this proof assumed that all graphs without odd cycles can be partitioned into 2 sets of vertices with different parity distance to a given vertex ?
This statement is clearly not true for graphs with odd cycle, but what makes it true for graphs without odd cycles?
Thanks
Sir wher is converse part it is if and only if condition
U only show if a graph has no odd cycle then it is bipartite but what about that is G is bipartite then it has no odd cycle
Thanks for watching! I only included what I think is the much harder part to prove in this video, which was also specifically requested by a viewer, and because of how long the video already is I didn't want to make it any longer. If you'd like, I'd be happy to do a video on the proof of the converse!
I was actually in the mood today to do a video on the converse, so I just recorded it. It will be out Sunday 12:00 am EDT. That's a weird time for people in America like me, but not many Americans are watching at this time of year, so I'm trying to release lessons at a time better for everyone else! Thanks for your support :)
Here's the lesson! ua-cam.com/video/xQcCXSFVSks/v-deo.html
Great explanation!
Glad it was clear, thanks a lot for watching!
So the v in "v is an element of V(G)" for the set X... is different than the v in "v is an element of of V(G)" for the set Y? I ask because you call them both v, but it seems to me like they can't both be the same vertex...
That is correct, assuming you mean around 7:40, calling them both is acceptable in this context of set builder notation. We could read it as "X is the set containing all vertices v in the graph G such that the distance between v and the vertex w is even." Then we read Y as "the set of all vertices v in G such that the distance between v and w is odd". In each case, v is ranging through all vertices of G that have a particular property in order to create each set. If we actually intended on using v to represent an arbitrary member of X, we would certainly need to use a different letter to represent an arbitrary member of Y.
great explanation
can you explain this - In a complete graph with n vertices there are n−1/2 edge-disjoint Hamiltonian cycles if n is an odd number and n≥3.
Thank you for watching! Sure, here is a very informal explanation.
A Hamiltonian cycle will contain two edges incident with each vertex (one to get there, and one to leave, so to speak). Each vertex is incident to n-1 edges by definition of a complete graph. Of course, n-1 is even if we assume n is odd. Then, if we take all of the edges incident to a vertex, and give pairs of them to as many Hamiltonian cycles as we can, we would give 2 edges to (n - 1)/2 Hamiltonian cycles. We also know that every other vertex needs to give 2 incident edges to each of these (n - 1)/2 Hamiltonian cycles, and of course we know each other vertex has exactly enough edges for that.
When we think of making the cycles as "giving edges", we assure that we have edge-disjoint cycles since once we give two edges to a cycle we cannot give those edges to another cycle. The idea of giving edges also suggests the division, as that is often how division is introduced. If you share n-1 apples with your (n-1)/2 friends, how many apples does each friend get? Of course the answer is 2. In our situation, we are asking, "If you must give away 2 apples to make a friend, and you have n-1 apples, how many friends can you make?" The answer is (n-1)/2. A silly explanation, but I hope it helps some!
Thanks a lot for your amazing explanation! Keep up with the great work ✌️
Very helpful video.. Thank u ...
Glad it helped, thanks for watching and if you're looking for more graph theory - check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Let me know if you ever have any video requests!
Hmmmm, wouldn't |P_2| = |Q_2|, necessarily (read: stronger claim than P_1 and P_2 having the same parity)? I'm assuming distance d(s, t) is the length of the shortest path between vertices s and t in the connected graph; |P| = d(w, a) and |Q| = d(b, w) are the same parity; |P_1| = |Q_1|; d(a, b) = 1.
PS: Awesome video -- thank you for sharing!
Really it was very helpful for me.
Glad to hear it, thanks for watching!
Can you prove isomorphism in bicyclic graphs? Thanks!
Can you prove by induction?
Please can you answer this question ::show that every closed odd walk contains an odd cycle
Really good 👍🏻
Thank you! If you're looking for more graph theory, check out my playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thanks, this helped a lot.
You're very welcome, I am glad it helped and thank you for watching!
Thank U for this awesome video.
My pleasure, thanks for watching!
thanks so much sir
You're very welcome! Thanks for watching and let me know if you ever have any lesson requests!
why do you assume G is a connected graph at the start of the proof?
Thanks for watching and good question! I mention early in the video that "A graph is bipartite if and only if all of its connected components are bipartite" (let me know if you'd like explanation of that fact). So that is why we only have to consider connected graphs, because if a graph is disconnected then we can just apply our proof to its connected components, proving each component is bipartite and thus the whole disconnected graph is as well. Does that help?
@@WrathofMath Yes, that answers my question, thanks!
thank you sir . with my best wishes
Thanks so much for watching!
Thanks a lot sir!
You're very welcome, thanks for watching! Let me know if you ever have any lesson requests!
Fantastico!
Thank you!
Awesome!!!
Thanks for watching!
Thanks !
You're welcome, thanks for watching!
Beautiful
I am doing gt without doing dm hope I Ge through ...
Thanks for watching and good luck! Let me know if you ever have any graph theory lesson requests!
marvellous
Thank you!
Are you a Computer Scientist or a mathematician? Since only a Computer Scientist starts counting with zero.
Haha, thanks for watching and good question! I've done a bit of programming, but I am no computer scientist! But us graph theorists benefit a lot by counting from 0 in a lot of situations, particularly when writing out the vertices of a walk! So when I put on my graph theory hat, I count from 0!
I am in 6th grade
That's awesome you're studying graph theory in 6th grade! I wish I had began studying it that early!
Also your arrows look like smiley faces
=)
Haha, I suppose they kind of do, I have never looked at them that way! If you can find subliminal images of happiness in my math lessons, all the better!
prove that Cn is a bipartite iff n is even.
Sir plz its prooof????
ł
Thanks for watching!
Amazing explanation!
Thank you! If you're looking for more graph theory, check out my graph theory playlist: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html