MA-351 Homework 2

Due at 4:59pm in my mailbox in SAS 3151, Tuesday, October 10, 2017

All solutions must be submitted in hardcopy either to me in class or placed in my mailbox. Note my office hours on my schedule.

1. Consider the generalization of Problem 4 of the 1st exam: A subgraph of the (n+1)st-dimensional hypercube is constructed by removing all edges {0b₂...b_n+1, 1b₂...b_n+1}, b_i ∈ {0,1}, except {00...0,10...0} and {01...1,11...1}. Overall, 2ⁿ-2 edges are removed. Please prove that the resulting subgraph has diameter n+1.

2. DMM, §2.4, Problem 11 on page 59.

3. Please consider a graph of n vertices that is a forrest of t trees, that is, t connected acyclic components. How may edges in terms of n and t does the forrest graph contain. Please prove your answer.

4. Please draw the binary tree (with left-right children distinguished) corresponding to the parenthesis expression ()()(((()))()())