Graphs and Networks: Bipartite Graphs

Graphs and Networks: Bipartite Graphs

Bipartite Graphs

Basic Characteristics

  • A Bipartite Graph is a type of graph where the vertices can be divided into two distinct groups or sets such that every edge in the graph connects a vertex from one set to a vertex from the other set.

  • Each vertex can be part of one set only and must not be linked to any vertex within the same set. Only cross connections are allowed.


  • Bipartite graphs can often be represented visually with each of their two sets of vertices grouped together.

  • A Complete Bipartite Graph denoted as K(m,n), is a special type of bipartite graph where every vertex of the first set is connected to every vertex of the second set, creating m*n edges.


  • Commonly used to model relationships between two different types of things: e.g., jobs and workers, students and courses, or people and clubs.

Common Properties

  • The degree of a vertex in a bipartite graph is the number of edges connected to it.

  • A bipartite graph does not contain any odd length cycles.

  • A graph is bipartite if and only if it is possible to colour the vertices of the graph using two colours such that no two adjacent vertices share the same colour.

  • If the vertices of a bipartite graph are all connected, it is called a connected bipartite graph.

  • In a bipartite graph, the Maximum Matching is the largest possible set of edges with no vertex shared between them.

  • In a weighted bipartite graph, the Minimum Cost Maximum Matching is a matching where the sum of the weights of all the edges is as small as possible.

The Bipartite Matching Algorithm

  • Algorithms such as the Hungarian Algorithm or the Hopcroft-Karp Algorithm can solve optimization problems related to bipartite graphs, such as the finding the Maximum Matching or the Minimum Cost Maximum Matching.