CS 230 : Discrete Computational Structures
Assignment #11 [Extra Credit]
For the problems below, explain your answers and show your reasoning.
1. [10 Pts] If G is a simple graph with n vertices and n edges, is G connected? If yes, give a
short justification. If no, give a counterexample.
No. Consider this beautifully drawn graph as a counter example:
2. [8 Pts] Consider a graph G that has 7 vertices with degrees of 5, 4, 3, 3, 2, 2, 1. How many
edges does G have? Explain.
By the Handshake Theorem: (5 + 4 + 3 + 3 + 2 + 2 + 1)/2 = 10 edges.
3. [12 Pts] Prove by induction that a complete binary tree of height h has 2h
leaves. Use the
inductive definition of complete binary trees.
(a) Base Case: A complete binary tree of height 0 has 1 leaf node 20
. The CBT of height
0 + 1 = 1 will have 2 leaves because by def of CBT’s, the CBT of the next height will
fill the left and right subtrees of all the current leaves. The # of leaves will double for
every increase in height by 1. So, 20 ∗ 2 = 21
(b) IH: A CBT of height k has twice the leaves of a CBT with height k−1. So, 2k−1 ∗2 = 2k
leaves
(c) Prove: CBT’s of height (k + 1) has twice the leaves of a CBT of height (k + 1) − 1 = k
(d) By IH, tree of height k has 2k
leaves
(e) n
k ∗ 2 = n
k+1 QED
4. [20 Pts] Prove that a graph is a tree if and only if it is acyclic but adding any edge will
create a cycle.
