CIS 160

Recitation Guide - Week 7

Topics Covered: Graphs, Probability (Inclusion-Exclusion, Conditional)

Problem 1:
Let T be a tree where the maximum degree is ∆. Prove that T has at least ∆ leaves.
Solution:
We will use the (non-standard) notation λ(T ) to denote the number of leaves in a tree T . Thus,
we can rewrite the claim as λ(T ) ≥ ∆(T ).
Direct Proof:
Let v ∈ V have degree ∆ in T = (V, E). Consider the subgraph induced on the vertices V \ {v}.
Each neighbor of v is in a distinct component in this graph, because we have destroyed the unique
path between any two of v’s neighbors in T . Thus there are ∆ components, each of which is a
tree.
There are two possibilities for each component. If a component is a single node, then this single
node is a leaf adjacent to v in T . If the component has at least 2 nodes, then it has at least 2 leaves.
One of the leaves may be adjacent to v and not a leaf in T . But the other leaf in this component
is still a leaf in T . In any case, each component contains at least one leaf of T and hence T must
have ∆ leaves.
Maximal Path:
Let v ∈ V have degree ∆. For each u
i , uj ∈ N (v), let Pi,j be a maximal path including ui − v − uj .
Note that there must be at least ∆ 2 such paths, since any pair of starting edges gives a different
path. We know that any such path pi,j must terminate in two leaves (call them wi,j and xi,j ).
Lastly, note that since there is a unique path between any two vertices in a tree, every pair of
leaves
admits

at most one maximal path. If there were λ(T ) < ∆ leaves, we would only have
λ(T ) ∆
2 < 2 distinct maximal paths, a contradiction; we must then have λ(T ) ≥ ∆.

Contradiction:
Assume that ∆ ≥ 2, since the cases of ∆ = 0 and ∆ = 1 are clearly true. Suppose for the sake of
contradiction that there are at most λ(T ) < ∆ leaves. For each ui ∈ N (v), let pi be a maximum
length path beginning with v, {v, ui }, ui . Note that there must be ∆ such paths. We know that
any such path pi must terminate in a leaf `i .
By the Pigeonhole Principle, where the pigeons are the terminating leaves of each path and the
holes are the λ(T ) leaves available, we know that, since λ(T ) < ∆, two paths share the same
terminating leaf, say `ω .
This is a contradiction, since there can only exist one unique path between `ω and v.
Induction on the number of vertices:
Let us prove this by induction on the number of vertices in the graph n.

1
We formulate a proposition P (n) which is: in a tree with n vertices and maximum degree ∆, the
number of leaves in the tree is at least ∆.
Induction Hypothesis: Assume that P (k) is true, for some k ∈ Z+ , k ≥ 3.
Base Case (n= 1, 2 and 3): The case of n = 1 is trivial - a graph of just 1 node has maximum
degree 0 and at least 0 leaves. There is only one possible tree when n = 2: T = (V, E), V = {u, v},
E = {{u, v}}. Here ∆ = 1, and we have 2 leaves, so it checks out as required.
There is only one possible tree when n = 3: T = (V, E), V = {u, v, w}, E = {{u, v}, {v, w}}. Here
∆ = 2, and we have 2 leaves, so it checks out as required.
We choose to show three base cases here to avoid a slightly unfortunate edge case in the Induction
Step.
Induction Step: Consider an arbitrary tree T = (V, E) such that |V | = k + 1 and it has maximum
degree ∆. Let ` ∈ V be an arbitrary leaf in T who has some neighbor a. Consider T 0 = (V 0 , E 0 )
where V 0 = V \ ` and E 0 = E \ {a, `}.
We know that |V 0 | = k and is a tree (since removal of a leaf can never disconnect a tree), so we can
apply the Induction Hypothesis on T 0 .
Note that there are two cases here:
1. a was the only vertex of degree ∆ in T .
It must be the case then that a has degree ∆ − 1 in T 0 and is of maximum degree. The
Induction Hypothesis gives us that T 0 must have at least ∆ − 1 leaves.
Further note if a is a leaf in T 0 , then it must be the case that n = 3 (convince yourself of
this), and that is already shown to be true by the base case. Hence, going forward we will
operate under the assumption that a is not a leaf.
Adding ` back to T 0 to reconstruct T increases the number of leaves by one (since a is not a
leaf), so we have that T has at least ∆ leaves.
2. There is some vertex in T 0 that has degree ∆.
By the Induction Hypothesis, we have that T 0 must have ∆ leaves.
There are two more cases here:
(a) a is a leaf in T 0
In this case, the addition of ` does not change the number of leaves, which means we
have at least ∆ leaves in T , as desired.
(b) a is not a leaf in T 0
In this case, the addition of ` increases the number of leaves by 1, which means we have
at least ∆ + 1 leaves in T , which proves our claim.
Induction on the number of edges:
You can do a similar procedure to the induction on the number of vertices in order to perform
induction on the number of edges. Note that in this case you would consider the subgraph induced
by the vertices other than the leaf.

2
Strong Induction on the number of edges:
Let us prove this by induction on the number of edges in the graph m.
We formulate a proposition P (m) which is: in a tree with m edges and maximum degree ∆, the
number of leaves in the tree is at least ∆.
Induction Hypothesis: Assume that P (j) is true, for all j ∈ Z, 1 ≤ j ≤ k, for some k ∈ Z+ ,
k ≥ 2.
Base Case (m=0, 1, 2): There is only one possible tree (of one vertex) when m = 0. Here ∆ = 0,
and we have at least 0 leaves.
There is only one possible tree when m = 1: T = (V, E), V = {u, v}, E = {{u, v}}. Here ∆ = 1,
and we have 2 leaves, so it checks out as required.
There is only one possible tree when m = 2: T = (V, E), V = {u, v, w}, E = {{u, v}, {v, w}}. Here
∆ = 2, and we have 2 leaves, so it checks out as required.
We choose to show two base cases here to avoid a slightly unfortunate edge case in the Induction
Step.
Induction Step: Let T be a tree with k + 1 edges and with a maximum degree ∆. Let v be a
vertex with degree ∆, and u be an arbitrary neighbor of v. Let us consider G0 = (V 0 , E 0 ), where
V 0 = V , E 0 = E \ {{u, v}}. Note that G0 must have had two connected components C1 and C2 ,
which are both trees when a subgraph is induced on each of them. Let C1 be the component with
v, and let C2 be the component with u.
There are two cases here:
1. There is another vertex in C1 that has degree ∆
From the induction hypothesis, we have that there must be ∆ leaves in C1 . Let us reconstruct
T from G0 .
There are two cases here:
(a) |C2 | = 1
In this case, if v is a leaf in G0 , then the addition of {u, v} will not change the number
of leaves. Therefore we have that T must have at least ∆ leaves. If v is not a leaf, then
the addition of {u, v} will add an additional leaf, so we have that T must have at least
∆ + 1 leaves.
(b) |C2 | ≥ 2
In this case, C2 must have two leaves. Hence there are at least ∆ + 2 leaves in G0 . Notice
that the addition of the edge {u, v} can decrease the number of leaves by up to 2 (if u
and v were both leaves in G0 ). Hence we have that T has at least ∆ leaves, as required.
2. v is the only vertex with degree ∆ in T .
Hence, ∆(C1 ) = ∆ − 1. From the induction hypothesis, we know that C1 must have ∆ − 1
leaves. We further note that if v is a leaf in G0 , it must be that m = 2 (convince yourself
of this), and we have already shown the validity of this in the base case. We will therefore
operate now under the assumption that v is not a leaf.

3
 There are two cases here:
(a) |C2 | = 1
Since v is not a leaf, then the addition of {u, v} will add an additional leaf, so we have
that T must have at least ∆ leaves.
(b) |C2 | ≥ 2
In this case, C2 must have two leaves. Hence there are at least ∆ + 1 leaves in G0 . Notice
that the addition of the edge {u, v} can decrease the number of leaves by up to 1 (if u
is a leaf in G0 ). Hence we have that T has at least ∆ leaves, as required.
Using inequalities:
We know that a tree with n vertices must have n − 1 edges. Since the sum of the degrees of all the
vertices in a graph must be twice the number of edges, we know that the total of all degrees in the
tree must be 2n − 2.
Let us consider the following partitioning of the vertices in V . Let A = {v ∈ V | deg(v) = ∆},
B = {v ∈ V | 1 < deg(v) < ∆}, and C = {v ∈ V | deg(v) = 1}. Note that V = A ∪ B ∪ C and
A ∩ B = ∅, A ∩ C = ∅, B ∩ C = ∅. Note that C is the set of leaves.

X
2n − 2 = deg(v)
v∈V
X X X
= deg(v) + deg(v) + deg(v)
v∈A v∈B v∈C
X
= ∆ · |A| + deg(v) + |C|
v∈B
≥ ∆ · |A| + |C| + 2 · |B|
= ∆ · |A| + |C| + 2 · (n − |A| − |C|) (since n = |A| + |B| + |C|)
= (∆ − 2) · |A| − |C| + 2n
≥ (∆ − 2) − |C| + 2n (since |A| ≥ 1)

Hence we have established that 2n − 2 ≥ (∆ − 2) − |C| + 2n. Further, we have that:

2n − 2 ≥ (∆ − 2) − |C| + 2n
−2 ≥ ∆ − 2 − |C|
|C| ≥ ∆

Hence we have that the number of leaves is at least ∆.

Minimal Counterexample:
Consider a minimal counterexample, i.e. a tree T which violates this property with the minimum
possible number of vertices, say m. We know that the case for m = 1, 2 can be handled easily, so
we may assume that m ≥ 3, i.e. the tree has at least 3 vertices. Now pick an arbitrary leaf ` and
name its only neighbor in the graph v; remove `. Consider the resulting graph T 0 . Note that T 0
has exactly m − 1 vertices. The following cases can occur:
Case 1: ∆(T ) = ∆(T 0 ).

4
Note that by removing a single leaf, we can never increase the number of leaves in the graph. It
follows that T 0 has at most as many leaves as T , i.e.

λ(T 0 ) ≤ λ(T ) < ∆(T ) = ∆(T 0 )

But this means λ(T 0 ) < ∆(T 0 ) and T 0 has m − 1 vertices. This is a contradiction, as we chose T to
be tree with the fewest vertices which violates the claim.
Case 2: v is a leaf in T 0 and ∆(T ) 6= ∆(T 0 ).
The only vertex whose degree can be affected by removing ` is v. Then v must have degree 1 and all
other vertices must have degree ≤ 1. The only trees for which this hold have exactly 1 or 2 vertices;
we already know that these cases do not violate the claim. As such, we have a contradiction (it’s
impossible for us to end up in this scenario).
Case 3: v is not a leaf in T 0 and ∆(T ) 6= ∆(T 0 ). If the maximum degree changes by removing this
leaf, that means that it must decrease by exactly one (we cannot increase degree by removing edges
and only removed one edge). In other words, ∆(T 0 ) = ∆(T ) − 1. Note that the number of leaves
in T 0 is λ(T ) − 1, since we removed ` and v is not a leaf. It follows that

λ(T 0 ) = λ(T ) − 1 < ∆(T ) − 1 = ∆(T 0 )

Again, λ(T 0 ) < ∆(T 0 ) and we have a contradiction, since T is not minimal.
In every case we have a contradiction - it must be the case that the set of counterexample is empty,
i.e. there are no trees which violate the claim, and we are finished.

5
Problem 2:
It is the Fall 2019 semester and Professor Gandhi is now teaching 3 full sections (001, 002, and 003)
of CIS 160. On any given day of classes, there is a 25 chance that he misses his first section, a 25
chance that he misses his second section, and a 51 chance that he misses his last section (and missing
one does not impact whether he misses the other). Using the inclusion-exclusion formula, calculate
the probability that on a given day, Professor Gandhi does not attend all of his classes.
Solution:
Let the sample space Ω be a set of 3-tuples, where any particular outcome can be expressed as
w = (w1 , w2 , w3 ), such that w1 , w2 , w3 are equal to 1 if Professor Ghandi attended sections 001, 002,
and 003 respectively, and 0 otherwise. Note that this sample space has a non-uniform probability
distribution.
Let A, B, C be the events in which Professor Gandhi misses Section 001, 002 and 003, respectively.
If he does not attend every class, then he must be missing at least one. Therefore, we are looking
for Pr[A ∪ B ∪ C].
By the Inclusion-Exclusion Principle,

Pr[A ∪ B ∪ C] = Pr[A] + Pr[B] + Pr[C]

− Pr[A ∩ B] − Pr[A ∩ C] − Pr[B ∩ C]
+ Pr[A ∩ B ∩ C]

Note that A, B, and C are independent events, so:

2 2 4
Pr[A ∩ B] = Pr[A] · Pr[B] = · =
5 5 25
2 1 2
Pr[B ∩ C] = Pr[B] · Pr[C] = · =
5 5 25
2 1 2
Pr[A ∩ C] = Pr[A] · Pr[C] = · =
5 5 25
2 2 1 4
Pr[A ∩ B ∩ C] = Pr[A] · Pr[B] · Pr[C] = · · =
5 5 5 125

Plugging it in, we have:

Pr[A ∪ B ∪ C] = Pr[A] + Pr[B] + Pr[C]

− Pr[A ∩ B] − Pr[A ∩ C] − Pr[B ∩ C]
+ Pr[A ∩ B ∩ C]
2 2 1 4 2 2 4
= + + − − − +
5 5 5 25 25 25 125
8 4
=1 − +
25 125
89
=
125

A faster way to solve the problem (without using inclusion-exclusion) is to notice the following

6
equality:

Pr[A ∪ B ∪ C] = 1 − Pr[(A ∪ B ∪ C)c ]

= 1 − Pr[Ac ∩ B c ∩ C c ]
= 1 − Pr[Ac ] · Pr[B c ] · Pr[C c ]

Note that
2 3
Pr[Ac ] = 1 − Pr[A] = 1 − =
5 5
2 3
Pr[B c ] = 1 − Pr[B] = 1 − =
5 5
1 4
Pr[C c ] = 1 − Pr[C] = 1 − =
5 5
So, we have that:

Pr[A ∪ B ∪ C] = 1 − Pr[Ac ] · Pr[B c ] · Pr[C c ]

3 3 4
=1− · ·
5 5 5
89
=
125

7
Problem 3:
You run into a town with 100 robots. You know that 99 of these robots tell the truth half the time
and lie the other half. You also that there is exactly 1 truthful robot in town, who always tells the
truth. You take a robot at random and ask a question seven times, and the robot tells the truth
every time. What is the probability that this is the truthful robot?
Solution:
We can define each outcome in the sample space Ω as an ordered pair, where the first element
represents whether or not the robot is truthful, and the second element is the robot’s answers to
the 7 questions, i.e. a sequence of length 7 of elements from {T,F}.
Let A be the event: selected robot is truthful. Let B be the event: selected robot tells the truth
seven times.
Note that from parsing the question, we know the following probabilities:
1 99
Pr(A) = Pr(A) =
100 100
 7
1
Pr(B|A) = 1 Pr(B|A) =
2

We want Pr(A|B) (make sure you can justify each step in this simplification):

Pr(A ∩ B)
Pr(A|B) =
Pr(B)
Pr(A) × Pr(B|A)
=
Pr(B)
Pr(A) × Pr(B|A)
= (Total Probability Theorem)
Pr(A ∩ B) + Pr(A ∩ B)
Pr(A) × Pr(B|A)
=
Pr(A) × Pr(B|A) + Pr(A) × Pr(B|A)
1
100 × 1
= 1 99 1 7
100 × 1 + 100 × ( 2 )
128
= ≈ 0.564
227