Bipartite Graphs

Introduction to Bipartite Graphs

  • A bipartite graph is a graph whose vertex set can be partitioned into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
  • In other words, a graph is bipartite if it is possible to split its set of nodes into two independent sets U and V such that every edge connects a node in U to a node in V.
  • Vertices in U are usually called part or side. For example, if a bipartite graph’s sides are label as U and V, we say the graph is (U,V)-bipartite.
  • It’s important to note that not every graph is a bipartite graph - there are certain conditions which must be met.

Categorising Bipartite Graphs

  • A bipartite graph is complete if every pair of vertices from different subsets has an edge between them. It is denoted as Kᵤ ₓ ᵥ, where u and v are the cardinalities of the two subsets.
  • A special type of bipartite graph is a tree, which is a connected graph without cycles.
  • A forest is a disjoint collection of trees, also a type of bipartite graph.

Testing If a Graph is Bipartite

  • One common technique is to perform a depth-first search (DFS) or breadth-first search (BFS) from any arbitrary starting vertex.
  • If during the search we find a vertex that has already been coloured, we check to ensure its colour is different from the current vertex’s colour.
  • If we find a vertex that has been coloured the same colour as the current vertex, the graph is not bipartite.

Properties of Bipartite Graphs

  • A graph is bipartite if and only if it has no odd-length cycles.
  • The maximum matching of a bipartite graph can be found using the Ford-Fulkerson algorithm.
  • In a bipartite graph, the sum of the size of the maximum matching and the size of a minimum vertex cover is equal to the number of vertices (Konig’s Theorem).
  • The chromatic number of a bipartite graph is always 2. That means we can colour the graph using only two colours.
  • The chromatic index or edge-colouring of a bipartite graph can be calculated using the Vizing’s theorem. Hence, understanding bipartite graphs is fundamental to learning about different types of graphs and their properties.