Trees

• Read 4.2, pages 87-92
  • When is a graph \(G\) called acyclic? What’s another name for such graphs?
  • When is a graph \(G\) called a tree?
  • Draw all trees of orders \(3\) and \(4\).
  • How can we define a tree alternatively using bridges instead of cycles?
  • What trees do we call stars, double-stars, caterpillars?
  • How does a rooted tree differ from a tree?
  • Prove theorem 4.2: A graph is a tree if and only if every two vertices are connected by a unique path.
  • Prove theorem 4.3: Every nontrivial tree has at least two end-vertices (leaves).
    • How does this theorem help us prove facts about trees?
  • Prove theorem 4.4: Every tree of order \(n\) has size \(n-1\).
  • Study example 4.5
  • Prove corollary 4.6: Every forest of order \(n\) with \(k\) components has size \(n-k\).
  • Practice problems: 4.7, 4.8, 4.13, 4.14
  • Prove theorem 4.7: Every connected graph of order \(n\) has size at least \(n-1\).
  • Prove theorem 4.8: If \(G\) is a graph of order \(n\) and size \(m\), then any two of the following imply that the graph is a tree (and hence also imply the third):
    1. \(G\) is connected
    2. \(G\) is acyclic
    3. \(m=n-1\)
  • Prove theorem 4.9: If \(T\) is a tree of order \(k\), then \(T\) is isomorphic to a subgraph of any graph \(G\) with \(\delta(G) \geq k-1\).
  • Practice problems: 4.20, 4.22