Bipartite Graph¶

Connection to Odd Cycles¶

A graph is bipartite if and only if it has no odd cycles. One direction of this theorem is clear because if a graph has an odd cycle, then in any partition into two sets, one set will contain more than half of the vertices of this cycle, and consequently, edges will be found within that set, meaning the graph is not bipartite.

So, we proceed to the second part. If it has no odd cycles, we know that the parity of the length of paths between two vertices is always constant. To prove this, suppose that between two vertices there is both an even-length path and an odd-length path. By joining these two paths, an odd-length closed walk is obtained, and in the previous section, we saw that if an odd-length closed walk exists in a graph, an odd cycle also exists, which contradicts the assumption.

Next, we assume that the graph is connected, because if it is not connected, the theorem can be proven for its components, concluding that each component is bipartite. Then, the first part of each component is designated as Part 1, and the second part as Part 2.

Consider an arbitrary vertex. Since the graph is connected, this vertex has either an odd-length path or an even-length path to every other vertex. We place vertices with odd-length paths into Set 1, and vertices with even-length paths into Set 2. To show that the graph is bipartite with these sets, we use proof by contradiction and assume that an edge exists within one set. In that case, there would exist both an odd-length path and an even-length path from the initial vertex to an endpoint of an edge within that set, which is a contradiction.

Existence of a Bipartite Subgraph with Half the Edges¶

Every graph with \(m\) edges has a subgraph with more than \(\frac{m}{2}\) edges. To prove this, consider the largest bipartite spanning subgraph. Take a vertex such that more than half of its edges are within its own partition (i.e., connect to other vertices within its partition set). If such a vertex does not exist, then the sum of degrees of vertices in the bipartite subgraph (considering only its edges) is greater than or equal to half the sum of degrees in the original graph, meaning greater than or equal to m, which implies the statement.

However, if such a vertex exists, we move that vertex to the other partition, and the edges that were on its own side (which are more than half its degree) now become cross-edges, resulting in more cross-edges than before, which contradicts the extremal assumption.