Bipartite Graph

What Does Bipartite Graph Mean?

A bipartite graph is a graph in which a set of graph vertices can be divided into two independent sets, and no two graph vertices within the same set are adjacent. In other words, bipartite graphs can be considered as equal to two colorable graphs. Bipartite graphs are mostly used in modeling relationships, especially between two entire separate classes of object.


A bipartite graph is also known as a bigraph.

Techopedia Explains Bipartite Graph

A bipartite graph has two sets of vertices, for example A and B, with the possibility that when an edge is drawn, the connection should be able to connect between any vertex in A to any vertex in B. If the graph does not contain any odd cycle (the number of vertices in the graph is odd), then its spectrum is symmetrical. The chromatic number, which is the minimum number of colors required to color the vertices with no adjacent vertices sharing the same colors, needs to be less than or equal to two in the case of a bipartite graph. All types of acyclic graphs (graphs which have no graph cycles), are examples of bipartite graphs. A cyclic graph is considered bipartite if all the cycles involved are of even length. According to Koning’s line coloring theorem, all bipartite graphs are class 1 graphs.

Bipartite graphs are widely used in modern coding theory apart from being used in modeling relationships.


Related Terms

Margaret Rouse

Margaret Rouse is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical, business audience. Over the past twenty years her explanations have appeared on TechTarget websites and she's been cited as an authority in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine and Discovery Magazine.Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages. If you have a suggestion for a new definition or how to improve a technical explanation, please email Margaret or contact her…