SME
Discrete Mathematics · Problem type
Trees and full m-ary trees
Use this for “A full 3-ary tree has 4 internal vertices. How many vertices, leaves and edges?”
This is an example. Type your own values to start a new problem.
n
=
m
×
i
+
1
l
=
(
m
−
1)
×
i
+
1
e
Edges
calculated
Formulas
n
=
m
×
i
+
1
13 = 3 × 4 + 1
l
=
(
m
−
1)
×
i
+
1
9 = (3 − 1) × 4 + 1
e
=
n
−
1
12 = 13 − 1
Assumptions
•
A tree is connected with no cycles, so a tree on n vertices has exactly n − 1 edges.
•
In a full m-ary tree every internal vertex has exactly m children, and leaves have none.
•
Every vertex but the root is the child of one internal vertex, so n = mi + 1.
Step-by-step
WE KNOW
m = 3, i = 4
FIND
vertices (n), leaves (l), edges (e)
Step 1 · Find vertices (n)
Use n = m × i + 1
Each
internal
vertex
has
m
children,
and
the
root
is
no
one’s
child.
n
=
3
×
4
+
1
n
=
12
+
1
n
=
13
Step 2 · Find leaves (l)
Use l = (m − 1) × i + 1
The
vertices
that
are
not
internal
are
leaves:
mi
+
1
−
i
.
l
=
(3
−
1)
×
4
+
1
l
=
2
×
4
+
1
l
=
8
+
1
l
=
9
Step 3 · Find edges (e)
Use e = n − 1
Each vertex but the root hangs from one edge.
e
=
13
−
1
e
=
12
Check
Put the numbers back in. Both sides should match.
13 = 3 × 4 + 1 ✓
9 = (3 − 1) × 4 + 1 ✓
12 = 13 − 1 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.