Bipartitions and Two-Colorings

Partitions and Color Assignments

A two-coloring is a way to encode a division of the vertices into two groups. It is useful when the groups represent two roles, types or states, with the requirement that adjacent vertices have different roles. The key is not that every possible edge between the groups must be present, but that no edge may have both endpoints in the same group.

Throughout, graphs are finite and simple. A coloring with palette \(\{\text{red},\text{blue}\}\) assigns one of these two colors to every vertex; it is proper if the endpoints of every edge receive different colors. Thus a proper coloring may use just one color when there are no edges. A bipartition of \(V(G)\) is a pair of disjoint sets \(X,Y\) whose union is \(V(G)\); either part is allowed to be empty.

The same condition can be checked in either language. In the partition language, inspect every edge and verify that it crosses from \(X\) to \(Y\). In the coloring language, inspect every edge and verify that its endpoint colors differ. In particular, vertices that are not joined by an edge are allowed to have the same color.

A bipartite graph need not be complete bipartite. For a bipartition \((X,Y)\), a complete bipartite graph has every possible edge between \(X\) and \(Y\); a general bipartite graph only requires that all its existing edges cross between the parts. The earlier material on complete bipartite graphs treats that more restrictive family.

The Correspondence

Proof. First suppose \(G\) is bipartite with parts \(X,Y\). Color every vertex of \(X\) red and every vertex of \(Y\) blue. By the definition of bipartition, each edge has one endpoint in \(X\) and one in \(Y\). Its endpoints therefore receive different colors, so the coloring is proper.

Conversely, suppose \(G\) has a proper coloring from the stated palette. Let \(X\) be the set of red vertices and \(Y\) the set of blue vertices. Each vertex receives exactly one color, so \(X\cap Y=\varnothing\) and \(X\cup Y=V\). Since the coloring is proper, no edge has both endpoints red or both endpoints blue. Every edge therefore has one endpoint in \(X\) and the other in \(Y\), so \((X,Y)\) is a bipartition. This also covers the graph with no vertices: both parts are empty, and the unique coloring of the empty vertex set is proper because there are no edges to check. \(\square\)

The theorem is a correspondence, not a requirement to find a special pattern of edges: once the vertex groups are chosen, the test is simply whether every edge crosses between them. Conversely, a proper red-blue assignment itself specifies the two groups. Exchanging red and blue exchanges \(X\) and \(Y\), without changing whether the coloring is proper.

Proof. Let \(uv\) be an edge. In a proper coloring, \(u\) and \(v\) must receive different colors, so both red and blue occur. If the graph has no edges, there is no edge whose endpoints could violate the properness condition. Hence assigning red to every vertex is proper (and the same argument works for blue). \(\square\)

Checking a Candidate Coloring

To verify a proposed coloring, write down the vertex sets and the full edge set first. Then list each edge and compare the colors of its two endpoints. A single edge with matching endpoint colors disproves properness; to verify properness, every edge in the edge set must pass. Checking only a selection of edges is not enough.

What the Edge Test Does—and Does Not—Say

For a proposed assignment on a specified graph, checking every edge is a complete test: if every edge has differently colored endpoints, the coloring is proper by definition; if an edge fails, it is not proper. This is a verification procedure for a candidate, not necessarily a method for finding one. When no candidate has been supplied, choosing colors that satisfy all edge constraints may require additional reasoning.

Keep the direction of the check straight. To show that a coloring is proper, account for every edge. To show that a particular coloring is not proper, one failing edge is enough. To show that a graph has no proper two-coloring, however, one failed candidate does not suffice: another assignment might work. The triangle example handles that stronger claim by considering both possible colors for one vertex and showing that each forces a contradiction.

Also distinguish the two parts from the edges. The parts partition the entire vertex set, including isolated vertices. Edges do not have to include every possible pair across the parts, and vertices in the same part need not all be adjacent. The defining restriction is only that no edge lies within a part.

Why the Correspondence Is Useful

The partition description is often convenient when a graph comes with two natural types of vertices. The coloring description is convenient for checking a proposed assignment: it turns the condition into a local test on each edge. The theorem lets us switch between these descriptions without changing the underlying requirement.

For example, if vertices represent tasks and an edge means that two tasks conflict, a proper red-blue coloring assigns tasks to two groups so that no conflicting pair is assigned to the same group. The model is valid only if every conflict is represented by an edge and the edge list is checked completely. An omitted edge could make an invalid assignment appear proper.

When recording a solution, give both the vertex set and the edge set (or an equivalent complete description of adjacency), state the two color classes, and check each edge. This makes the claim independently verifiable and makes errors—such as overlooking an edge within one part—easy to locate.