## Description

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.