Print bookPrint book

Try It Now

Site: Saylor Academy
Course: CS202: Discrete Structures
Book: Try It Now
Printed by: Guest user
Date: Wednesday, May 14, 2025, 4:43 AM

Description

Work these exercises to see how well you understand this material.

Table of contents

Exercises

  1. Given the following vertex sets, draw all possible undirected trees that connect them.
    1. Va = {right, left}
    2. Vb= {+, −, 0}
    3. Vc= {north, south, east, west}.

  2. Prove that if G is a simple undirected graph with no self-loops, then G is a tree if and only if G is connected and |E|= |V| − 1.

    Hint. Use induction on |E|.

    1. Prove that any tree with at least two vertices has at least two vertices of degree 1.
    2. Prove that if a tree has n vertices, n ≥ 4, and is not a path graph, Pn, then it has at least three vertices of degree 1.

 

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Solutions

  1. Answer: The number of trees are: (a) 1, (b) 3, and (c) 16. The trees that connect Vc are:



  2. Hint: Use induction on |E|.

  3. Answer:
    1. Assume that (V, E) is a tree with |V| ≥ 2, and all but possibly one vertex in V has degree two or more.

      \(\begin{align*} 2|E| = \sum_{v \in V} \mathrm{deg}(v)) \geq 2|V|-1 &\Rightarrow |E| \geq |V| - \frac{1}{2} \\ &\Rightarrow |E| \geq |V| \\ &\Rightarrow (v,E) \mathrm{is \; not \; a \; tree} \end{align*}\)

    2. The proof of this part is similar to part a in that we can infer 2|E|≥ 2|V| - 1, using the fact that a non-chain tree has at least one vertex of degree three or more.