Bipartite Graph Definition
A Bipartite Graph G is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.
Few points about the Bipartite Graph.
- A Bipartite Graph can be represented as Km,n where m is the number of vertices in set U and n is the number of vertices in set V.
- The above point deduces the fact that the total number of vertices in the Bipartite graph is m + n
- The maximum number of edges in such a graph would be m * n
Above is an image of K3,4. Notice that in a Bipartite Graph, it is not necessary that each vertex from U should connect to each vertex in V. Assume that the orange vertices are in set U and the green vertices are in set V
Cyclic Bipartite Graph
A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. Note that it is possible to color a cycle graph with even cycle using two colors. For example, see the following graph. example 2:
It is not possible to color a cycle graph with odd cycle using two colors:
The Complete Bipartite Graph
The Bipartite Graph G is said to be a Complete Bipartite Graph each vertex in U is connected to each vertex in V.
Below is an image of K3,4 which is a Complete Bipartite. Assume that the blue vertices are in set U and the red vertices are in set V.
Note: Similar to Bipartite Graphs there can be Tripartite Graphs as well. That will have three disjoint sets of vertices. May be V1, V2 and V3 and rest all the conditions remain same as Bipartite graphs.