# 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.