Complete Bipartite Graphs and Their Partitions

Partitions Restrict Which Edges Can Appear

A vertex partition can describe a graph by separating its vertices into two groups and restricting edges to run between the groups. For example, one group might represent one type of object and the other group a second type; an edge records a relation between objects of different types. The same partition also gives a direct count of how many edges could be present at most. This tutorial develops that count and the complete bipartite graphs that attain it.

Throughout, graphs are finite and simple: they have no loops or multiple edges. A partition of a set \(V\) into two parts \(X\) and \(Y\) means that \(X\cap Y=\varnothing\) and \(X\cup Y=V\). Either part is allowed to be empty. An edge \(uv\) is a cross-edge for this partition if one endpoint lies in \(X\) and the other lies in \(Y\).

Definition: A graph \(G=(V,E)\) is bipartite with parts \(X,Y\) if \(X,Y\) partition \(V\) and every edge has one endpoint in \(X\) and one endpoint in \(Y\). It is a complete bipartite graph with parts \(X,Y\) if its edge set consists of all such cross-edges, with no other edges. When \(|X|=r\) and \(|Y|=s\), a complete bipartite graph is denoted \(K_{r,s}\).

The part sizes determine the number of cross-edges available, but a bipartite graph need not use all of them. Completeness is relative to the specified parts: a missing cross-edge is allowed in a bipartite graph, but not in a complete bipartite graph with those parts.

This definition is different from that of a complete graph. In a complete graph \(K_n\), every pair of distinct vertices is adjacent. In \(K_{r,s}\), only pairs with one vertex in each part are adjacent; pairs within either part are not. The notation \(K_{r,s}\) records the two part sizes, not an edge count.

Counting the Allowed Edges

Theorem: Let \(G=(V,E)\) be bipartite with specified parts \(X,Y\), where \(|X|=r\) and \(|Y|=s\). Then \(|E|\le rs\). Equality holds exactly when \(G\) is complete bipartite with those parts.

Proof. Consider the set \(X\times Y\) of ordered pairs \((x,y)\) with \(x\in X\) and \(y\in Y\). Each pair determines one possible edge \(xy\). Conversely, each edge of \(G\) joins a unique vertex \(x\in X\) to a unique vertex \(y\in Y\), so it determines exactly one pair \((x,y)\). Thus the possible cross-edges are in one-to-one correspondence with \(X\times Y\), which has \(rs\) elements. Since every edge of \(G\) must be one of these cross-edges, \(|E|\le rs\). Equality holds precisely when every possible cross-edge is present, which is exactly the definition of a complete bipartite graph with parts \(X,Y\). This also covers an empty part: if \(r=0\) or \(s=0\), then \(rs=0\), and no cross-edge can exist. \(\square\)

The count \(rs\) comes from making one choice from each part, not from choosing two vertices from the whole vertex set. Each choice gives one distinct edge. In particular, there is no extra factor of \(1/2\): the pair is counted once by specifying its endpoint in \(X\) first and its endpoint in \(Y\) second.

For a complete bipartite graph \(K_{r,s}\), every vertex in the part of size \(r\) is adjacent to all \(s\) vertices in the other part, and so has degree \(s\). Every vertex in the part of size \(s\) has degree \(r\). These degree counts provide a second way to check the edge total: summing the degrees over the first part counts every edge exactly once, giving \(rs\).

Takeaway: For a fixed partition \(X,Y\), the permitted edge set is exactly \(\{xy:x\in X,\ y\in Y\}\). A bipartite graph uses some subset of these edges; a complete bipartite graph uses the entire set, whose size is \(|X||Y|\).

Worked Examples

Worked Example: Listing Every Edge of \(K_{3,2}\)

Let \(X=\{a,b,c\}\), \(Y=\{1,2\}\), and \(V=X\cup Y\). The complete bipartite graph with these parts has edge set

E=\{a1,a2,b1,b2,c1,c2\}.

There are \(r=3\) vertices in \(X\) and \(s=2\) in \(Y\), so the formula gives \(rs=3\cdot2=6\) edges. Directly from the list, \(|E|=6\). For a second check, each of \(a,b,c\) has degree \(2\); summing degrees over \(X\) gives \(2+2+2=6\), counting every edge once. The two vertices of \(Y\) each have degree \(3\), which gives \(3+3=6\) as another check. Every listed edge crosses the partition, and all six possible cross-edges appear, so the graph is complete bipartite with these parts.

Worked Example: A Bipartite Graph That Is Not Complete

Take \(X=\{a,b,c\}\) and \(Y=\{1,2,3\}\), and define \(G=(V,E)\) by \(V=X\cup Y\) and

E=\{a1,a2,a3,b1,b3,c2,c3\}.

Each listed edge has one endpoint in \(X\) and one in \(Y\), so this graph is bipartite with the specified parts. There are \(3\cdot3=9\) possible cross-edges, while the edge list has \(7\) edges. The two missing cross-edges are \(b2\) and \(c1\). Hence this graph is not complete bipartite with these parts.

Check: The degrees of \(a,b,c\) are \(3,2,2\), respectively, so their sum is \(3+2+2=7=|E|\). The degrees of \(1,2,3\) are \(2,2,3\), respectively, and \(2+2+3=7\) as well. The total agrees with the edge list. Since \(7<9\), the graph does not attain the maximum possible edge count for these parts.

Worked Example: Constructing \(K_{2,4}\)

Let \(X=\{p,q\}\) and \(Y=\{1,2,3,4\}\). Define \(G=(V,E)\) using \(V=X\cup Y\) and

E=\{p1,p2,p3,p4,q1,q2,q3,q4\}.

The part sizes are \(r=2\) and \(s=4\), so the complete bipartite graph should have \(rs=2\cdot4=8\) edges. The list contains four edges incident with \(p\) and four incident with \(q\), for \(4+4=8\) edges. Each of \(p,q\) has degree \(4\), and each of \(1,2,3,4\) has degree \(2\). Summing degrees over \(X\) gives \(4+4=8\); summing over \(Y\) gives \(2+2+2+2=8\). Every possible cross-edge is listed, so the graph is \(K_{2,4}\).

The same count also describes the shape of this graph: the two vertices in \(X\) are each joined to all four vertices in \(Y\), while no two vertices within \(X\) or within \(Y\) are adjacent. The total order is \(2+4=6\) vertices, and the edge count is \(8\).

Part Sizes and Special Cases

The notation permits a part of size zero. For example, if \(X=\varnothing\) and \(Y=\{u,v,w\}\), then \(V=Y\) and there are no possible cross-edges. The complete bipartite graph \(K_{0,3}\) therefore has vertex set \(\{u,v,w\}\) and edge set \(\varnothing\). Its edge count is \(0\cdot3=0\). It is complete bipartite relative to this partition because every possible cross-edge is present: there simply are no such edges.

If one part has size \(1\), the formula gives \(1\cdot s=s\). Thus \(K_{1,s}\) has one vertex joined to each of the \(s\) vertices in the other part, and no edges among those \(s\) vertices. For \(s=0\), this is the one-vertex graph with no edges. For \(s=1\), it is a graph on two vertices with one edge. These cases follow from the same definition and count; they do not require separate rules.

The order of the two part sizes does not affect the isomorphism type: \(K_{r,s}\) and \(K_{s,r}\) are isomorphic. To see this, take a complete bipartite graph with parts \(X,Y\) of sizes \(r,s\), and another with parts \(Y',X'\) of sizes \(s,r\). Choose bijections from \(X\) to \(X'\) and from \(Y\) to \(Y'\). Together they give a bijection of the vertex sets, and a pair is an edge exactly when it has one endpoint in each part. The bijection therefore preserves adjacency in both directions, as required for an isomorphism. The notation is consequently symmetric in its two indices.

Common Mistake: Counting Vertices Instead of Cross-Pairs

A frequent error is to add the part sizes to get the number of edges. For \(K_{3,2}\), the incorrect calculation \(3+2=5\) counts the vertices, not the edges. The correct count is \(3\cdot2=6\), because each of the three vertices in one part can be paired with each of the two vertices in the other part.

Another possible error is to divide the product by \(2\), as in the usual count of unordered pairs chosen from one set. Here each edge is already counted once by the unique ordered choice \((x,y)\) with \(x\in X\) and \(y\in Y\). Dividing \(3\cdot2\) by \(2\) would incorrectly give \(3\) edges, omitting half of the six cross-pairs.

Finally, seeing that every edge crosses the partition proves only that the graph is bipartite with those parts. To establish that it is complete bipartite, check that every cross-pair is an edge, or equivalently that the edge count is \(rs\). A short edge list with no within-part edges may still omit permitted cross-edges.

Check Your Understanding

For each question, use the specified partition when deciding which edges are permitted.

For parts \(X=\{a,b\}\) and \(Y=\{1,2,3\}\), list all edges of the complete bipartite graph and calculate its edge count.
A bipartite graph has parts of sizes \(4\) and \(5\), and has \(17\) edges. How many possible cross-edges are missing?
Explain why a graph with parts \(X=\varnothing\) and \(|Y|=6\) has no possible cross-edges, and state the complete bipartite graph's edge count.
For \(K_{2,5}\), calculate the degree of a vertex in each part and use the degrees in one part to check the edge count.
A graph has parts of sizes \(3\) and \(4\), and its edge set contains every possible cross-edge. What is its edge count, and why is it complete bipartite with those parts?