Bipartite Graph¶

Relation to Odd Cycles¶

A graph is bipartite if and only if it contains no odd cycles. One direction of this theorem is obvious: 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, resulting in edges within that set, meaning the graph is not bipartite.

Now, let us consider the other direction. If the graph has no odd cycles, we know that the parity (even/odd) of the path lengths between any two vertices remains constant. To prove this, assume there exist both an even-length path and an odd-length path between two vertices. Combining these two paths would create a closed walk of odd length. In previous sections, we saw that if a closed walk of odd length exists in a graph, then an odd cycle must also exist, which contradicts our assumption.

Next, we assume the graph is connected. If it is not connected, the theorem can be proven for each connected component separately. We can then conclude that each component is bipartite and assign the first part of each component as "Part 1" and the second part as "Part 2."

Choose an arbitrary vertex. Since the graph is connected, this vertex will have either an odd-length path or an even-length path to every other vertex. Place vertices with odd-length paths from the initial vertex into "Set 1" and those with even-length paths into "Set 2." To prove that the graph is bipartite with these sets, we use proof by contradiction: assume there exists an edge within one set. This would imply the existence of both an odd-length path and an even-length path from the initial vertex to the endpoints of this edge, leading to a contradiction.

Existence of a Bipartite Subgraph with Half the Edges¶

Every graph with \(m\) edges contains a bipartite subgraph with more than \(\frac{m}{2}\) edges. To prove this, consider the largest spanning bipartite subgraph. Suppose there exists a vertex where more than half of its edges are within its current partition. If no such vertex exists, the sum of degrees in the subgraph would be at least half the sum of degrees in the original graph (i.e., at least \(m\)), from which the claim follows.

However, if such a vertex exists, move it to the other partition. This increases the number of edges in the subgraph by more than half of its degree, contradicting the assumption of maximality.