---
title: "Define bipartite graph with example"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:define-bipartite-graph-example"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/define-bipartite-graph-example
site: BCT Engineering
---

# Define bipartite graph with example

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2074 Bhadra, 2 marks; 2070 Bhadra, 3 marks (asked 2 times)
- Video: [What is a Bipartite Graph? | Graph Theory](https://www.youtube.com/watch?v=HqlUbSA9cEY) — Wrath of Math
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/define-bipartite-graph-example
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Define bipartite graph with suitable 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.

## Answer

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 vertex | Adjacent vertices (all in V2) |
|---|---|
| a | x, y, z |
| b | x, 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. A graph is bipartite if:
   A. It has no edges
   B. Every vertex has even degree
   C. It is complete
   D. Vertices split into two sets with every edge joining the two sets
   Answer: D. No edge lies inside V1 or inside V2. (Key point: Definition)

2. Equivalent condition for bipartiteness:
   A. It has no odd-length cycle
   B. It has no even cycle
   C. It is a tree only
   D. It has no vertex of degree 3
   Answer: A. Bipartite is equivalent to 2-colorable and to having no odd cycles. (Key point: Odd cycles)

3. How many edges does the complete bipartite graph K(2,3) have?
   A. 5
   B. 6
   C. 3
   D. 9
   Answer: B. K(m,n) has mn edges: 2 x 3 = 6. (Key point: K(m,n))

## Related in Discrete Structure

- [Complete and bipartite graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Acomplete-and-bipartite-graph) — Discrete Structure, chapter 4