Transcript Each connected graph has a spanning tree.

MATH 310, FALL 2003
(Combinatorial Problem Solving)
Lecture 11, Wednesday, September 24
A Spanning Tree




Each connected graph has a spanning
tree.
For finite graphs the proof is easy. [Keep
removing edges that belong to some
circuit].
For infinite graphs this is not a theorem
but an axiom that is equivalent to the
renowned axiom of choice from set
theory.
Note: A spanning subgraph H of G
contains all vertices of G.
How many spanning trees
are there in Kn?




For example, on the
right we see that K3
has 3 spanning trees!
Let t(Kn) denote the
number of spanning
trees in the completre
graph Kn. We know
that t(K3) = 3.
Theorem 4 (Cayley,
1889): t(K n) = nn-2
Proof: Bijective proof
(principle of equality):
Prüfer sequences
(codes)!
Two Remarks


Remark 1: We are
counting all spanning
trees. [Some may be
isomorphic].
Remark 2: Counting
all spanning trees in a
complete graph Kn is
the same as counting
all labeled trees on n
vertices.
Prüfer Sequence From a
Labeled Tree

7
4
3
1
2
8

5
6
Delete the leaf with
the largest label and
print the label of its
neighboor!

We are given a tree
whose vertices are
labeled (from 1 to n).
Following the rule on
the left we form a
sequence s1, s2, ...,
sn-2 of length n-2.
Each element of the
sequence is a number
from 1 to n.
The sequence [s1, s2,
..., sn-2] is called the
Prüfer code or
sequence.
The Steps of Prüfer Recipe
7
3
2


4
1
5
8
6
Delete the leaf with
the largest label and
print the label of its
neighboor!





Delete 7, print 1.
Delete 6, print 8.
Delete 5, print 1.
Delete 4, print 1.
Delete 2, print 3.
Delete 3, print 8.
The sequence:

[1,8,1,1,3,8]
From the Sequence to the
Tree.


7
2
1
4
8
6
5
3


Add an edge between the
vertex labeled by the
current sequence element
and the leaf with maximal
label.
Examle: [2,3,2,8,2,1].
Numbers (between 1 and
8), missing in the sequence
represent the leaves of a
tree. ki v kodi manjkajo, so
listi drevesa.
Maximal leaf: 7
First sequence element: 2

Edge:
Edge:
Edge:
Edge:
Edge:
Edge:

Final edge: 1~2.





7~2.
6~3.
5~2.
4~8.
8~2.
3~1.
Leaves: [4,5,6]
Leaves: [3,4,5]
Leaves: [3,4]
Leaves: [3,8]
Leaves: [2,3]
Leaves: [1,2]
Rooted Trees, Binary Trees

Some new terms:
•
•
•
•
•
•
•
•
•
root
level number
parent
child
sibling
leaf (leaves)
internal vertex
m-ary tree
binary tree
Theorem 2

Let T be an m-ary tree
with n vertices, of which
i vertices are internal.
Then,
• n = m i + 1.

On the left we have
•
•
•
•

n = 25,
#leaves = l = 13,
i = 12.
n = 2i + 1.
Proof: Each internal
vertex gives rise to m
edges. The tree has
therefore m i edges. It
hase m i + 1 vertices.
Corollary

Let T be an m-ary tree with n
vertices, i internal vertices, and l
leaves. Then:



(a) Given i, l = (m-1)i + 1, n = mi + 1
(b) Given l, i = (l – 1)/(m – 1), n = (ml – 1)/(m-1)
(c) Given n, i = (n – 1)/m, l = [(m – 1)n + 1]/m.
Example 1
If 56 people sign up for a tennis
tournament, how many matches will
be played? [Hint: binary tree].
 Answer: 55 matches.
 [Every player but winner played
exactly one match in which he or
she lost and these are all the
matiches]

Rooted Trees – More New
Terms

More new terms:
• The height of a
rooted tree
• balanced rooted tree

Note: the binary
tree on the left is
not balanced but
the right subtree
is.
Theorem 3

Let T be an m-ary
tree of height h
with l leaves. Then


(a) l · mh, and if all
leaves are at height
h, l = mh.
(b) h ¸ d logml e,
and if the tree is
balanced, h = d
logml e.
3.2 Search Trees and
Spanning Trees

Homework (MATH 310#4W):
• Read 4.1.
• Do Exercises 3.2: 2,4,8,10,12,16,22,28
• Volunteers:
• ____________
• ____________
• Problem: 28.

On Monday you will also turn in the list of all
new terms (marked).