Trees

• An acyclic graph is called a forest.
• A connected forest is a tree.
• A spanning tree of G=(V,E) is a spanning subgraph that is a tree.
• Exercise: Let G=(V,E) be a graph on m nodes. Show that the following statements are equivalent:
  1. G is a spanning tree.
  2. There is a unique path between each pair of nodes.
  3. G contains m-1 edges and is connected.
  4. G contains m-1 edges and is acyclic.
  5. G is acyclic and connected.
• Exercise: Show that if G=(V,E) is a spanning tree and then contains exactly one cycle. (This cycle is the fundamental cycle for this spanning tree and edge.)

  Exercise: Show that if C is the edge set of the fundamental cycle and if the edge then the graph is also a spanning tree.