Introduction of Bipartite Graph

Definition and Properties

A bipartite graph is a type of graph in which the set of vertices can be divided into two distinct sets such that no two vertices within the same set are adjacent. In other words, every edge in the graph connects a vertex from one set to a vertex in the other set.

A bipartite graph $G = (V, E)$ consists of:

• Two disjoint sets of vertices, say $U$ and $V$, such that $U \cap V = \emptyset$.
• Edges that only connect vertices between $U$ and $V$, meaning no edge exists within $U$ or within $V$.

A bipartite graph can be represented as:

$$G = (U, V, E)$$

where:

• $U$ and $V$ are the two sets of vertices.
• $E$ is the set of edges where each edge $(u, v)$ satisfies $u \in U$ and $v \in V$.

Conditions for Bipartiteness

A graph is bipartite if and only if it does not contain an odd-length cycle. This can be checked using:

1. Graph Coloring: If a graph can be colored using two colors such that no two adjacent vertices have the same color, it is bipartite.
2. BFS or DFS Traversal: A graph traversal can determine whether the graph can be split into two sets without internal edges.

Examples

1. Complete Bipartite Graph $K_{m,n}$: A bipartite graph where every vertex in set $U$ is connected to every vertex in set $V$.
2. Real-World Applications:
   • Matching Problems: Job assignments, student-project assignments.
   • Social Networks: Representation of user-item interactions in recommendation systems.
   • Biological Networks: Protein interaction networks.