Graph theory · Definition
Bipartite graph
Before you start you need to know
Bipartition models matchings, such as students with courses or workers with tasks, and is the simplest way to split a graph into two opposing sides.
Definition
A bipartite graph is a graph \(G=(V,E)\) whose vertices split into two disjoint sets \(A\) and \(B\) so that every edge \(e\in E\) joins a vertex of \(A\) to one of \(B\).
The two parts \(A\) and \(B\) have no internal edges: everything that happens in the graph happens between one side and the other. That is why a bipartite graph cannot have triangles, nor odd cycles in general. Conversely, the classical criterion says a graph is bipartite exactly when all its cycles have even length.
To decide whether a connected graph is bipartite, put one vertex in side \(A\), its neighbors in \(B\), their neighbors in \(A\), and so on. If at some point an edge joins two vertices of the same side, there is an odd cycle and the graph is not bipartite. In a connected graph the partition, when it exists, is unique up to swapping \(A\) and \(B\); each connected component contributes the same degree of freedom.
The guiding example is the complete bipartite graph \(K_{m,n}\), with parts of \(m\) and \(n\) vertices and all \(mn\) possible edges between them. With \(N\) vertices, a bipartite graph has at most \(\lfloor N^2/4\rfloor\) edges. Also, since each edge has one endpoint in each part, the degree sum over \(A\) equals the degree sum over \(B\), and both equal \(|E|\). A common mistake is to believe that having no triangles is enough: a 5-cycle has no triangles and is not bipartite either.
Think about it
Is the cube graph bipartite, with 8 vertices (the triples of 0s and 1s) and edges between triples that differ in exactly one coordinate?
Yes. Taking as \(A\) the triples with an even number of ones and as \(B\) those with an odd number, each edge changes the parity and hence joins the two parts.
If a connected bipartite graph has \(|A|\ne|B|\), can the roles of \(A\) and \(B\) be swapped?
Only as names: the partition is unique, so \(A\) and \(B\) are the only two possible sides and swapping them only changes what we call them.
Exercises 10
- Which of the following graphs is bipartite?
- How many edges does the complete bipartite graph \(K_{2,5}\) have, where each vertex of one part is joined to every vertex of the other?
- What is the maximum number of edges in a bipartite graph with 6 vertices?
- Which of these conditions guarantees that a graph is NOT bipartite?
- A graph has vertices \(1,\dots,6\) and edges \(\{1,4\},\{1,5\},\{2,4\},\{2,6\},\{3,5\},\{3,6\}\). Which is a valid partition \(A\), \(B\)?
- To the cycle \(C_6\), with vertices \(1,\dots,6\) and edges \(\{i,i+1\}\) and \(\{6,1\}\), one edge is added. Which one makes it non-bipartite?
- In a bipartite graph, the 4 vertices of part \(A\) all have degree 3 and the 6 vertices of \(B\) all have the same degree \(d\). What is \(d\)?
- A connected bipartite graph has parts of 3 and 5 vertices. What is the minimum number of edges it can have?
- A graph on 7 vertices has three connected components: two isolated edges and a path on 3 vertices. In how many ways can the unordered partition \(\{A,B\}\) be chosen?
- Can a graph with 9 vertices and 21 edges be bipartite?
References
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.2
- Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.1
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.2