Bipartite Graphs and Explicit Bipartitions

Describing a Bipartition

A bipartite graph is described by separating its vertices into two classes and checking that every edge goes between the classes. This is a concrete way to verify bipartiteness from a vertex and edge list: the proposed classes must account for every vertex, and no listed edge may have both endpoints in the same class. The graph is finite and simple throughout, so edges join distinct vertices and there are no multiple edges.

The conditions on \(X\) and \(Y\) do different jobs. Their union must include every vertex, including isolated vertices; their intersection must be empty, so that each vertex belongs to exactly one class. The edge condition is then checked for every edge \(uv\in E\): either \(u\in X,v\in Y\), or \(u\in Y,v\in X\). In particular, an edge with both endpoints in \(X\), or both in \(Y\), invalidates the proposed bipartition.

For a graph given by lists, a reliable verification has three steps: first check that the classes are disjoint; next check that together they contain exactly \(V\); finally inspect every edge and confirm that its endpoints lie in opposite classes. Checking only a sample of the edges is not enough to verify a bipartition.

Bipartitions and Two-Colorings

A two-coloring assigns one of two colors to each vertex. It is called proper when adjacent vertices receive different colors. The two colors can be represented by the classes \(X\) and \(Y\), so this viewpoint gives an equivalent description.

Proof. Suppose first that \(X,Y\) is a bipartition. Give every vertex in \(X\) the first color and every vertex in \(Y\) the second color. By the definition of bipartition, each edge has one endpoint in each class, so its endpoints have different colors. This is a proper two-coloring.

Conversely, suppose every vertex has been assigned one of two colors and every edge joins vertices of different colors. Let \(X\) be the set of vertices with the first color and \(Y\) the set with the second color. Each vertex received exactly one color, so \(X\cap Y=\varnothing\) and \(X\cup Y=V\). The coloring condition says every edge joins different colors, hence one endpoint is in \(X\) and the other is in \(Y\). Thus \(X,Y\) is a bipartition. The argument also covers an edgeless graph: every coloring is proper when there are no edges. \(\square\)

This equivalence is useful as a way to think about a proposed split, but explicit classes make verification especially direct. When starting from an edge list, write down the two classes and check each listed edge against them.

Isolated Vertices and Disconnected Graphs

An isolated vertex has degree zero, meaning that no edge is incident with it. Since the bipartition condition applies to edges, an isolated vertex imposes no restriction on which class it occupies. It must still be placed in one of the two classes, because \(X\cup Y\) must equal \(V\).

Likewise, if a graph has several connected components, the edge check still applies to the entire edge list. There are no edges between different components, so the choice of classes in one component does not directly constrain the choice in another. For an explicit bipartition, it is enough to give classes covering the whole graph and verify all its edges; no connectedness assumption is needed.

How Many Edges Can Join Two Classes?

Once a bipartition is specified, each possible edge must use one vertex from each class. There are \(|X||Y|\) such cross-class pairs: for each of the \(|X|\) choices in \(X\), there are \(|Y|\) choices in \(Y\). This gives an edge bound, with an exact description of when equality occurs.

Proof. Because the graph is simple, there is at most one edge for each unordered pair of distinct vertices. The bipartition condition says every edge is a pair with one endpoint in \(X\) and the other in \(Y\). There are exactly \(|X||Y|\) such pairs, so the number of edges cannot exceed \(|X||Y|\). If equality holds, all these possible pairs must be edges: having even one missing pair would leave fewer than \(|X||Y|\) edges. Conversely, if every cross-class pair is an edge, there is one edge for each of the \(|X||Y|\) pairs, giving equality. If either class is empty, there are no cross-class pairs and the edge condition forces \(E=\varnothing\); the inequality and equality characterization still hold. \(\square\)

When a Proposed Split Fails

A candidate pair of classes can fail in two different ways: it may not be a partition of the vertices, or it may be a partition but have an edge inside one class. Separating these checks helps diagnose mistakes. In particular, a failed edge check cannot be repaired by ignoring that edge; the proposed classes must be changed, or the graph is not bipartite.

Common Pitfalls

Leaving out an isolated vertex. If a vertex does not occur in the edge list, it is easy to forget it when writing the classes. But the classes must partition \(V\), not just the vertices incident with edges. Put each isolated vertex in either class.

Checking only whether the classes are disjoint. Disjoint classes may still fail to cover the vertex set. For example, if \(V=\{1,2,3\}\), then \(\{1\}\) and \(\{2\}\) are disjoint but omit vertex \(3\). Check both disjointness and union before checking edges.

Checking only some edges. A single edge within one class disproves the proposed bipartition, even if every other edge crosses. For instance, the wrong calculation “\(pq\) and \(qr\) cross, so the triangle \(pqr\) is bipartite” overlooks \(rp\): after \(p\in X\), \(q\in Y\), and \(r\in X\), edge \(rp\) has both endpoints in \(X\). The correction is to check every listed edge, not merely two of them.

Assuming the classes must have equal size. The definition imposes no such condition. In \(K_{2,3}\), the two classes have sizes two and three, yet every edge joins opposite classes. The relevant requirement is about endpoints of edges, not the sizes of the classes.