K₃,₄
7 vertices, 12 edges
m + n and mn.
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.
This page is easier if you are comfortable with:
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).
A complete bipartite graph joins every vertex of one group to every vertex of the other.
The number of edges is the product of the part sizes.
These examples are worked by hand, step by step, so you can compare your own working.
How many edges has ?
How many edges has ?
How many edges has ?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
7 vertices, 12 edges
m + n and mn.
vertices in the 3-part have degree 4
Joined to every vertex of the other part.
needs m and n both even
All degrees even.
9 edges; non-planar
Kuratowski graph.
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.
How many edges does K₃,₄ have?
What are the degrees in K₃,₄?
Does K₄,₆ have an Euler circuit?
For which m, n does K_{m,n} have a Hamiltonian cycle?
7 ✗
12 ✓
Edges are mn.
edges inside parts ✗
none ✓
Parts are independent sets.
deg = m for the m-part ✗
deg = n ✓
Degree is the other part’s size.
K₃,₄ has an Euler circuit ✗
K₃,₄ has odd degrees ✓
Needs both even.
Try each one on paper, then open the answer. Use the solver above to see the full working.
10
7
36
30
8
28
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
mn.
n for the m-part, m for the n-part.
When m and n are both even.
No.
bipartite graphs.
Kuratowski’s theorem.
More in Discrete maths and number theory and the formula sheets.