Summary of "Graph Theory 11: Trees"

Main Ideas and Concepts:

Definition of a Tree:
- A Tree is defined as a connected graph that contains no cycles.
- A cycle is described as a collection of distinct Edges and Vertices that form a closed loop.
Importance of Trees:
- Trees are significant in data storage and representation, exemplified by Family Trees where relationships can be visualized hierarchically.
Properties of Trees:
- Leaves: Trees contain Vertices with a degree of exactly one, known as Leaves.
- Unique Paths: Any two Vertices in a Tree are connected by exactly one unique path, unlike in graphs with cycles where multiple paths may exist between Vertices.
- Edge Count: For a Tree with n Vertices, there are n - 1 Edges. This property can be verified through a specific example and mathematical induction.

Induction Proof for Edge Count:
- Base Case: For n = 2 (two Vertices), there is one edge connecting them.
- Inductive Step: Assume true for K Vertices. For K + 1 Vertices:
  - Remove a leaf (vertex with degree 1) and its connecting edge from the Tree.
  - This results in a Tree with K Vertices, maintaining the property that the number of Edges is one less than the number of Vertices.
  - Conclude that the original Tree had K + 1 Vertices and K Edges, thus confirming the relationship n - 1.

A Tree can be defined in various equivalent ways:
- As a connected graph without cycles.
- As a graph where every two Vertices are connected by unique paths.
- As a graph with n Vertices and n - 1 Edges.