Skip to main content

Define bipartite graph with example

Short answer

A bipartite graph's vertices can be split into two sets with all edges going between the sets. No edges inside a set. Example: K2,3 has two vertices on one side, three on the other, and all 6 cross edges.

Define bipartite graph with suitable example.

A graph G = (V, E) is bipartite if its vertex set can be split into two disjoint sets V₁ and V₂ such that every edge joins a vertex of V₁ to a vertex of V₂ (no edge inside V₁ or inside V₂).

Equivalent statements:

  • G is 2-colorable (χ(G) ≤ 2).
  • G has no cycle of odd length.

A complete bipartite graph K_{m,n} has |V₁| = m, |V₂| = n and every possible edge between them, so it has mn edges.

Example: K_{2,3}: V₁ = {a, b}, V₂ = {x, y, z}; edges ax, ay, az, bx, by, bz (6 edges).

V1 vertexAdjacent vertices (all in V2)
ax, y, z
bx, y, z

Other examples: every even cycle (C₄, C₆), every tree, and the cube Q₃. The triangle K₃ and the pentagon C₅ are not bipartite because they contain odd cycles.

Uses: matching (jobs and applicants), scheduling.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →