SME
Discrete Mathematics · Problem type
Edges of complete graphs
Use this for “How many edges has K₇? How many has the complete bipartite graph K₃,₄?”
This is an example. Type your own values to start a new problem.
Eₙ
=
×
(
−
1)
2
Epq
=
p
×
q
d
Degree in Kₙ
calculated
Formulas
d
=
n
−
1
6 = 7 − 1
Eₙ
=
n
×
n
− 1
2
21
=
7
×
7 − 1
2
Epq
=
p
×
q
12 = 3 × 4
Assumptions
•
Kₙ is simple and joins every pair of its n vertices by one edge, so each vertex has degree n − 1.
•
Each edge of Kₙ is one pair of vertices, so Kₙ has C(n, 2) = n(n − 1) ÷ 2 edges.
•
The complete bipartite graph has p vertices on one side and q on the other, and joins every vertex to every vertex across.
Step-by-step
WE KNOW
n = 7, p = 3, q = 4
FIND
degree in Kₙ (d), edges of Kₙ (Eₙ), bipartite edges (Epq)
Step 1 · Find degree in Kₙ (d)
Use d = n − 1
Each vertex is joined to every other vertex.
d
=
7
−
1
d
=
6
Step 2 · Find edges of Kₙ (Eₙ)
Use Eₙ = n × (n − 1) ÷ 2
n
vertices
each
meet
n
−
1
edges,
and
every
edge
is
counted
from
both
its
ends.
Eₙ
=
7
×
7 − 1
2
Eₙ
=
7
×
6
2
Eₙ
=
42
2
Eₙ = 21
Step 3 · Find bipartite edges (Epq)
Use Epq = p × q
Each
of
the
p
vertices
is
joined
to
all
q
across.
Epq = 3 × 4
Epq = 12
Check
Put the numbers back in. Both sides should match.
6 = 7 − 1 ✓
21
=
7
×
7 − 1
2
✓
12 = 3 × 4 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.