---
title: "Complete and bipartite graph"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:complete-and-bipartite-graph"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/complete-and-bipartite-graph
site: BCT Engineering
---

# Complete and bipartite graph

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2075 Bhadra, 5 marks
- Video: [What are Complete Bipartite Graphs? | Graph Theory, Bipartite Graphs](https://www.youtube.com/watch?v=iKeA1c-bdXM) — 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/complete-and-bipartite-graph
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Describe complete graph and bipartite graph.

## Short answer

A complete graph K_n has an edge between every pair of distinct vertices, n(n-1)/2 edges, each vertex degree n-1. A bipartite graph's vertices can be partitioned into two sets with edges only between sets; it has no odd cycles. Complete bipartite K_{m,n} has all mn edges between the two parts.

## Answer

#### Complete graph Kₙ
A simple graph in which every pair of distinct vertices is joined by exactly one edge.
- n vertices, n(n − 1)/2 edges, each vertex has degree n − 1 (so it is regular).
- χ(Kₙ) = n; K₁, K₂, K₃, K₄ are planar; K₅ and larger are not.

```text
 K3:  a           K4:  a ---- b
     / \               | \  / |
    b---c              |  \/  |
                       |  /\  |
                       d ---- c
```
(K₄ is drawn with both diagonals.)

#### Bipartite graph
A graph whose vertices can be divided into two disjoint sets V₁ and V₂ such that every edge joins a vertex in V₁ to one in V₂.
- It is bipartite if and only if it has no odd cycle, or equivalently it is 2-colorable.
- A **complete bipartite graph K_{m,n}** has all mn edges between V₁ (m vertices) and V₂ (n vertices).

Example K_{2,3}: V₁ = {a, b}, V₂ = {x, y, z}, with edges from each of a and b to each of x, y, z (6 edges). K₃,₃ has 9 edges and is non-planar.

| Property | Kₙ | K_{m,n} |
|---|---|---|
| Vertices | n | m + n |
| Edges | n(n − 1)/2 | mn |
| Chromatic number | n | 2 |
| Bipartite? | Only for n ≤ 2 | Yes |

## Check yourself

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

1. The complete graph Kn has how many edges?
   A. n(n - 1)/2
   B. n^2
   C. n(n + 1)/2
   D. n - 1
   Answer: A. Every pair of n vertices is joined once. (Key point: Edges of Kn)

2. The chromatic number of Kn is:
   A. 2
   B. n
   C. n - 1
   D. 3
   Answer: B. All vertices are mutually adjacent so each needs its own color. (Key point: Chromatic number)

3. A graph is bipartite iff it:
   A. Has no even cycle
   B. Is complete
   C. Has no odd cycle
   D. Has all vertices of even degree
   Answer: C. Equivalently it is 2-colorable. (Key point: Bipartite test)

4. K(3,3) has how many edges?
   A. 6
   B. 3
   C. 12
   D. 9
   Answer: D. K(m,n) has mn edges: 3 x 3 = 9. (Key point: K(m,n))

## Related in Discrete Structure

- [Define bipartite graph with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adefine-bipartite-graph-example) — Discrete Structure, chapter 4, asked 2×