Proof: If a Graph has no Odd Cycles then it is Bipartite | Graph Theory, Bipartite Theorem
ฝัง
- เผยแพร่เมื่อ 2 ต.ค. 2024
- A graph has no odd cycles if and only if it is bipartite. One direction, if a graph is bipartite then it has no odd cycles, is pretty easy to prove. The other direction, if a graph has no odd cycles then it is bipartite, is quite a bit harder to prove! In this video, we focus on the difficult direction! In this video math lesson we prove that if a graph has no odd cycles then it is bipartite!
This is a wonderful theorem that I love because it is not obviously true, and so a proof of it is very fascinating! There are several proofs of this theorem, as there are with most any theorem, and there is a shorter proof than this one that I have seen. But I think this proof is more straightforward, so I offer it in this video, and maybe we'll go over a different proof another time. Also, we'll go over the other direction in another lesson as well, but try to prove it yourself!
In this proof, we use the definition of bipartite, and we use an argument by contradiction. We partition the vertex set of our graph into a set of vertices that are an even distance away from a particular vertex, and a set of vertices that are an odd distance away from that particular vertex. Then we assume for the sake of contradiction that this is not a bipartite partitioning, and we find that this forces a contradiction! It's a great proof, so I hope you enjoy this lesson!
So, if you want to know if a graph is bipartite, one way you can check is by checking to see if it has any odd cycles. If it has no odd cycles, then we can say with absolute certainty that it is bipartite! Another theorem we use, right at the beginning of the proof, is that a graph is bipartite if and only if all of its connected components are bipartite. Try proving this yourself if you're not familiar with it, it's pretty straightforward! This theorem allows us to focus our proof only on connected graphs, because as long as we can prove a graph's connected components are bipartite, we have proved the whole graph is bipartite!
I hope you find this video helpful, and be sure to ask any questions down in the comments!
I am playing a song I wrote at the end, and it does not have a name yet.
+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
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
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?
How did your exam go?
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?
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! :)
Thanks so much for making this clear! I pray to have professors who can articulate just like you!
Thank you!
isn't proof over at 13:52 if we say [wab] is closed odd walk hence it should contain odd cycle hence contradiction
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...
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!
Sean your explanations are honestly awesome! These help me form my own conclusions and get to the proof myself! Thank you so much ☺️
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.
@Wrath_of_Math can you please do a series on discontinuous dynamics?
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
No odd cycles? More like "Nice proof that excites us!" 🙏
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: th-cam.com/video/ZmakwnZv-qo/w-d-xo.html
@@WrathofMath Thank you so much! It makes more sense now.
This question came up in one of my CS assignments. Thanks
Glad it helped, thanks 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.
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! th-cam.com/video/xQcCXSFVSks/w-d-xo.html
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 ✌️
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!
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.
Thanks, this helped a lot.
You're very welcome, I am glad it helped and thank you for watching!
Please can you answer this question ::show that every closed odd walk contains an odd cycle
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!
Thanks a lot sir!
You're very welcome, thanks for watching! Let me know if you ever have any lesson requests!
Loved the explanation, thanks! :D
So glad it helped! Thanks for watching!
Can you prove isomorphism in bicyclic graphs? Thanks!
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!
Very good and elaborate proof man! Thanks
You’re welcome, thanks for watching! I am glad it was clear!
Can you prove by induction?
thanks so much sir
You're very welcome! Thanks for watching and let me know if you ever have any lesson requests!
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!
marvellous
Thank you!
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!
Beautiful
Thank U for this awesome video.
My pleasure, thanks for watching!
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! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Let me know if you ever have any video requests!
Really it was very helpful for me.
Glad to hear it, thanks for watching!
Fantastico!
Thank you!
Tanks!! Really good explanation!
You're welcome, I am glad it helped! Let me know if you ever have any questions!
thank you sir . with my best wishes
Thanks so much for watching!
ł
Thanks for watching!
Great explanation, fun to watch!
Thank you, I'm glad to hear it!
Absolutely brilliant!
Thank you!
Amazing explanation!
Thank you! If you're looking for more graph theory, check out my graph theory playlist: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Really good 👍🏻
Thank you! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Great explanation!
Glad it was clear, thanks a lot for watching!
Thanks !
You're welcome, thanks for watching!
Awesome!!!
Thanks for watching!
prove that Cn is a bipartite iff n is even.
Sir plz its prooof????