Bipartite graph

Simple_bipartite_graph;_two_layers

Simple_bipartite_graph;_no_crossings

Biclique_K_3_5_bicolor

Heawood_graph_bipartite_(bicolor)

Odd_Cycle_Transversal_of_size_2

Bipartite graph

A bipartite graph is a special type of graph in the field of graph theory. A graph is bipartite if its set of vertices can be divided into two disjoint sets such that no two graph vertices within the same set are adjacent. In other words, every edge in the graph connects a vertex in the first set to a vertex in the second set.

Definition

Formally, a graph \( G = (V, E) \) is bipartite if the vertex set \( V \) can be partitioned into two disjoint sets \( U \) and \( W \) such that every edge in \( E \) connects a vertex in \( U \) to a vertex in \( W \). This can be written as: \[ U \cup W = V \] \[ U \cap W = \emptyset \] \[ \forall (u, v) \in E, u \in U \text{ and } v \in W \]

Properties

• A graph is bipartite if and only if it does not contain any odd cycles.
• The chromatic number of a bipartite graph is 2, meaning it can be colored using two colors such that no two adjacent vertices share the same color.
• Bipartite graphs are also known as 2-colorable graphs.

Examples

• The simplest example of a bipartite graph is the complete bipartite graph \( K_{m,n} \), where every vertex in set \( U \) is connected to every vertex in set \( W \).
• Trees are bipartite graphs because they do not contain any cycles, let alone odd cycles.

Applications

Bipartite graphs have numerous applications in various fields:

• In computer science, they are used in matching problems and network flow algorithms.
• In sociology, bipartite graphs can model relationships between two different classes of objects, such as people and the clubs they belong to.
• In biology, they can represent interactions between two different species, such as plants and their pollinators.

Related Concepts

• Matching (graph theory)
• Network flow
• Graph coloring
• Complete bipartite graph
• Tree (graph theory)
• Cycle (graph theory)

See Also

• Graph theory
• Vertex (graph theory)
• Edge (graph theory)
• Chromatic number
• Odd cycle