Let me remind you that we defined bipartite graphs as follows. We say that a graph G is bipartite if its vertices can be partitioned into two disjoint sets, L and R such that every edge connects the vertex from L to a vertex from R. Or in other words, there are no edges connecting two vertices from the same part. And in this case, we call L and R the parts of the graph G. Here's an example of bipartite graphs. We color all vertices of one part red and all vertices of the other part blue. And now we can see that every edge connects a red vertex to a blue vertex. Here is an equivalent definition of bipartite graphs. We can say that a graph is bipartite if and only if it has no cycles of odd length. A bipartite graph can have cycles of even lengths. It can have cycles of lengths four, six, eight. But it can never have a cycle of odd length. Let's prove that this definition is equivalent to the original one, to the one that we already know. First, let's prove that if we have a bipartite graph, graph G, with parts L and R such that every edge goes from L to R, then there are no cycles of odd length. Indeed, when you try to find a cycle in a bipartite graph, each edge takes you to a different part of the graph. So if you want to return to the original vertex of a cycle, then you have to make an even number of steps. So it can only have cycles of even length, and a bipartite graph never has cycles of odd length. Now let's prove the other direction. Assume we have a graph without odd cycles. We want to prove it's bipartite. We want to construct two parts L and R such that all edges go from L to R. If graph is not connected then we will prove it for every connected component of it. And then we'll conclude that the whole graph is bipartite. If every connected component is bipartite, then the whole graph is bipartite too. So we fix some connected component, C1 and then we fix a vertex in this component. We'll color it red. Now for every other vertex on this connected component, we check if there is a path of odd lengths from v, to this vertex, then we'll color it blue. Otherwise, we color it red. And we want to say that this is a good partition, that all edges now go from red to blue vertices. How do I prove it? So let's pick some vertex. Let's pick the vertex V and color it red. Now if there is a path from V to some other vertex of odd lengths, we color it blue. And this is a set of blue vertices. For example, there exists a path of lengths one from V to V8, or the path of lengths three from V to V8. That's why we color it in blue. And all the remaining vertices, we color red. Since this is connected component there is a path from V to V3 and we know that there are no path of odd lengths. So there must be only even length paths from V to V3. So we know that there is a path of even length from V to every red vertex. Now let's prove that this partition is good, that all edges go from blue to red vertices. Assume there was contradiction, there is an edge between two red vertices, for example, between V5 and V7. What does it mean? V7 is colored red, which means there is a path of even length from V to V7, here it is. V5 is also colored red, this means there is a path of even length from V to V5. And now we also add this edge between V5 and V7. We have even plus even plus 1 edge, this is a cycle of odd length. But we know that our graph doesn't have cycles of odd length, we reach a contradiction. Assume again towards contradiction there is an edge between two blue vertices. Then again, there is a path of odd lengths from V to V1, there is a path of odd lengths from V to V2, and there is an edge between V1 and V2. Odd plus odd plus 1 is odd. So again, we get a cycle of odd lengths, but we know our graph doesn't have such cycles. So this means that all edges go from red vertices to blue vertices, this graph is bipartite. Formally we'll say that this partition is good because there are no edges between blue and red vertices. And then we just repeat the same procedure for every single connected component of the graph. If every component is bipartite, the graph is bipartite.