Discrete Mathematics - Mathematics 210 - Fall 2010

Definition: A graph is called a tree if (a) it has no simple circuits, and (b) it is connected.

Remark: Do you see why we call it a "tree"? Because, in real life, trees have no circuits; i.e.,  tree branches do not join back together, right? Actually, in "real life", sometimes weird things happen: look at this picture!

1. Suppose a graph has 4 vertices, labeled a, b, c, d. And suppose it has the following edges: ab, ac, ad. Is this graph a tree?
2. Draw each of the following graphs and explain why each of them is or isn't a tree:
   1. Vertices: a, b, c, d, e.  Edges: ab, bc, cd, de, da.
   2. Vertices: a, b, c, d, e, f.  Edges: ab, cd, ce, cf.
3. In the definition above, why do we say no simple circuits? (Why do we need to say "simple"?)
4. Prove or disprove: removing any edge of a tree disconnects it.
5. Prove or disprove: every tree has at least one vertex of degree 1.
6. 1. True or false: every tree that has exactly 3 edges has exactly 4 vertices. Prove your answer.
   2. True or false: every tree that has exactly n edges has exactly n+1 vertices. Prove your answer.
7. When people talk about their "family tree", is it really a tree? Justify your answer.