What is Bipartite Graph?
A simple graph G(V, E) is called Bipartite Graph if it’s vertices can be partitioned into two disjoint sets – V1 and V2, such that no edge connects vertices belonging to the same set ( or every edge in G connects a vertex in V1 and a vertex in V2).
For Example,
No edges in the above graph connect vertices belonging to the same set. Thus, the graph is bipartite.
Complete Bipartite Graph
What is a Complete Bipartite Graph?
A Bipartite Graph in which each vertex in set V1 is connected to all vertices in set V2. In other words, all vertices in one set are adjacent to every vertex in the other set.
Complete Bipartite Graph is represented as Kn,m, n is the number of vertices in set 1, and m is the number of vertices in set 2. Example,
In the above two graphs, every vertex in one set is connected to all vertices in the other set. Thus, they are complete bipartite graphs.
Regular Bipartite Graph
What is a regular bipartite graph?
A bipartite graph in which each vertex has the same degree is known as a regular bipartite graph.
Chromatic Number of Bipartite Graph
Every Bipartite Graph is two chromatic. It means we can color the vertices of the bipartite graph using two distinct colors such that no two adjacent vertices have the same color. Consequently, every 2-chromatic graph is bipartite.
We can color a bipartite graph by assigning one color to vertices in set V1 and other color to vertices in set V2.
Note: Bipartite graphs are not strictly 2-chromatic. A null graph (graph with no edges) is bipartite but it is 1-chromatic.
Number of Bipartite Graphs
Suppose a bipartite graph with distinct vertices. Let n and m be the number of vertices in set V1 and V2 respectively.
Maximum number of edges = n * m
Number of distinct bipartite graphs = 2n*m
Properties of Bipartite Graph
- Every bipartite graph has chromatic number 2 and vice-versa.
- Every tree is bipartite.
- No bipartite graph can contain an odd cycle.
- The bipartition of a bipartite graph is unique if and only if the graph is connected. Unique bipartition means we cannot split vertices in set V1 and V2 in more than one way.
- Every hypercube is bipartite.
- Every bipartite graph is a perfect graph.
- Subgraphs of a bipartite graph are also bipartite.
- If any subgraph of a given graph is not bipartite, then the graph is not bipartite.
- The sum of the degree of vertices in set V1 is equal to the sum of the degree of vertices in set V2.
Read
- Prove bipartite graph is 2-chromatic
- Show that a graph is bipartite if and only if it does not have a cycle of odd length