1. Proof: Every tree with $n$ vertices has $n-1$ edges

Definitions:

• A tree is a connected, undirected graph with no cycles.
• $n$ is the number of vertices in the tree.
• $m$ is the number of edges in the tree.

Proof by induction on $n$:

---

Base case ($n = 1$):

• A tree with one vertex has no edges (since it cannot connect to another vertex).
• For $n = 1$, $n-1 = 0$, which matches $m = 0$. The base case holds.

---

Inductive hypothesis:

• Assume that any tree with $k$ vertices has exactly $k-1$ edges ($m = k-1$).

---

Inductive step ($k+1$ vertices):

1. Start with a tree $T_k$ that has $k$ vertices and $k-1$ edges (by the inductive hypothesis).
2. Add one new vertex $v$ and one edge connecting $v$ to any vertex of $T_k$. This creates a new tree $T_{k+1}$, which:
   • Remains a tree (connected, no cycles).
   • Now has $k+1$ vertices.
   • Adds exactly one edge to $T_k$, so the total number of edges becomes $k-1+1 = k$.

By induction, every tree with $n$ vertices has $n-1$ edges.

---

2. Proof: A connected graph with $n$ vertices and $n-1$ edges is a tree

Definitions:

• A connected graph means there is a path between every pair of vertices.
• A tree has no cycles.

Proof:

1. Assume the graph is connected and has $n$ vertices and $n-1$ edges.

   • Since the graph is connected, there are no disconnected components.

2. Suppose the graph has a cycle.

   • A cycle means at least one edge can be removed while keeping the graph connected.
   • Removing one edge would make the total number of edges $m = n-2$, which contradicts the given condition $m = n-1$.

   Hence, the graph has no cycles.

3. Conclusion:

   • A connected graph with $n$ vertices and $n-1$ edges is acyclic and connected.
   • Therefore, it satisfies the definition of a tree.

---

Would you like further clarification or examples? Here are some additional questions to explore:

1. Can you give an example of a tree with $n = 5$ vertices and verify the edge count?
2. What happens if a graph has $n$ vertices but more than $n-1$ edges?
3. Can you construct a non-tree graph with $n = 5$ vertices and $n-1$ edges?
4. How does this relate to the Euler characteristic for planar graphs?
5. Why is connectivity a crucial part of the definition of a tree?

Tip: Use the relationship $m = n-1$ to quickly verify if a graph can be a tree!