Complete Bipartite Graph Explained with Worked Examples

The complete bipartite graph has two parts of sizes and , with every vertex of one part joined to every vertex of the other. It has edges.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Complete bipartite graph means

has edges, has 25, and the star has 6 (one centre joined to six leaves). In each vertex in the first part has degree and each in the second has degree ; the sum of the degrees is , twice the number of edges (the handshaking lemma). The count is a use of the product rule (the counting product rule).

It is the densest bipartite graph for the given parts, so a bipartite graph on vertices has at most edges (bipartite graphs). is non-planar (9 edges exceed , the planar graph bound) and one of the two Kuratowski graphs (Kuratowski's theorem). It has a perfect matching when (Hall's marriage theorem).

The chromatic number is 2 (two colours, one per part), and Hamiltonian cycles exist only when (Dirac's theorem gives ; has none). The complement of is two disjoint complete graphs (the complement of a graph).

What is it used for?

A complete bipartite graph joins every vertex of one group to every vertex of the other.

How to use complete bipartite graph

  1. Identify the part sizes .
  2. Edges .
  3. Degrees are and .
  4. Check the handshaking identity .

Graph

Edges of K1,6, K3,4 and K5,5: 6, 12, 25K1,6: 6K3,4: 12K5,5: 2500.511.522.533.540510152025Edges of K1,6, K3,4 and K5,5: 6, 12, 25graphyGraph with x from 0 to 4 and y from 0 to 28. Shows bars (3); point K1,6: 6 at (1, 6); point K3,4: 12 at (2, 12); point K5,5: 25 at (3, 25).

The number of edges is the product of the part sizes.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: K₃,₄

How many edges has ?

Worked example
Answer
1212
  1. Formula

Example 2: K₅,₅

How many edges has ?

Worked example
Answer
2525
  1. Formula

Example 3: the star K₁,₆

How many edges has ?

Worked example
Answer
66
  1. Formula

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

K₃,₄

7 vertices, 12 edges

m + n and mn.

Degrees

vertices in the 3-part have degree 4

Joined to every vertex of the other part.

Euler circuit

needs m and n both even

All degrees even.

K₃,₃

9 edges; non-planar

Kuratowski graph.

Word problems

K_{m,n} has m + n vertices and mn edges. Vertices in the m-part have degree n and vice versa. It has an Euler circuit iff m and n are both even.

Edges

How many edges does K₃,₄ have?

  1. 3 × 4
  2. Check: ✓12.

Degrees

What are the degrees in K₃,₄?

  1. 3-part vertices4
  2. 4-part vertices3
  3. Check: 3 × 4 + 4 × 3 = 24 = 2 × 12 ✓4 and 3.

Euler circuit Higher

Does K₄,₆ have an Euler circuit?

  1. Degrees 6 and 4, all even
  2. Check: ✓Yes.

Hamiltonian Higher

For which m, n does K_{m,n} have a Hamiltonian cycle?

  1. m = n ≥ 2
  2. Check: K₃,₃ has one ✓m = n ≥ 2.

Common mistakes

Edges = m + n

7 ✗

12 ✓

Edges are mn.

Thinking vertices within a part are joined

edges inside parts ✗

none ✓

Parts are independent sets.

Wrong degree

deg = m for the m-part ✗

deg = n ✓

Degree is the other part’s size.

Odd × even Euler circuit

K₃,₄ has an Euler circuit ✗

K₃,₄ has odd degrees ✓

Needs both even.

Exam tips

  1. Edges mn.
  2. Degrees swap.
  3. Euler: m, n even.
  4. Hamiltonian: m = n.
  5. Non-planar when m, n ≥ 3.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Edges in K₅,₂ Foundation

10

2. Vertices in K₅,₂ Foundation

7

3. Edges in K₆,₆ Foundation

36

4. Degree sum in K₃,₅ Higher

30

5. Edges in K₁,₈ Higher

8

6. Edges in K₄,₇ Higher

28

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Complete bipartite graph
Every cross pair is an edge.
Part
One of the two vertex sets.
Degree
Edges at a vertex.
Independent set
No internal edges.
Kuratowski graph
K₅ or K₃,₃.
Hamiltonian
Has a spanning cycle.

Frequently asked questions

How many edges has K_{m,n}?

mn.

What are its degrees?

n for the m-part, m for the n-part.

When has it an Euler circuit?

When m and n are both even.

Is K₃,₃ planar?

No.

Which page covers bipartite graphs?

bipartite graphs.

Which page covers Kuratowski’s theorem?

Kuratowski’s theorem.

More in Discrete maths and number theory and the formula sheets.