Рет қаралды 35,091
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: www.patreon.com/wrathofmathlessons
Follow Wrath of Math on...
● Instagram: wrathofmathedu
● Facebook: WrathofMath
● Twitter: wrathofmathedu
My Music Channel: kzbin.info