Bipartite Graphs

Definition of Bipartite Graphs

• A bipartite graph is a graph whose vertices can be divided into two disjoint sets so that every edge connects a vertex in one set to a vertex in the other set.
• This partitioning division creates a two-colouring of the graph, where vertices in one set are one colour, and vertices in the other set are a different colour. No two adjacent vertices share the same colour.
• The two sets that the vertices are divided into are often referred to as parts or sides.

Characteristics of Bipartite Graphs

• A graph is bipartite if and only if it is acyclic and every cycle of the graph has even length.
• Bipartite graphs do not contain any odd-length cycles.
• If a graph is bipartite, it must always be possible to colour it using only two colours, which is not the case for all graphs.
• An empty graph, a graph without edges, is technically a bipartite graph, as no vertices share an edge.

Complete Bipartite Graphs

• A complete bipartite graph, K_{m,n}, is a special sort of bipartite graph where there’s an edge between every vertex in one set to every vertex in the other set. Here, m and n represent the count of vertices in the two distinct sets.
• In K_{m,n}, each vertex in the first set is connected to exactly n vertices in the second set, and each vertex in the second set is connected to exactly m vertices in the first set.

Bipartite Graph Applications

• Bipartite graphs are often used to model relationships where there are two distinct classes of objects, such as in job assignment problems where one set contains people and the other contains jobs.
• Bipartite graphs are also used in network flow problems. Here, the source and sink neither belong to part one nor part two.