Proof: If $G$ is a connected graph with $n$ vertices and $n-1$ edges, then $G$ is a tree.

Definitions:

1. A tree is a connected acyclic graph.
2. A spanning tree of a graph $G$ is a subgraph that:
   • Includes all the vertices of $G$,
   • Is connected,
   • Has no cycles.

The Proof:

To prove that $G$ is a tree, we need to establish two properties:

1. $G$ is connected.
2. $G$ has no cycles.

---

Step 1: $G$ is given as connected.

By assumption, $G$ is a connected graph. This satisfies the first requirement of a tree.

---

Step 2: $G$ has no cycles.

Suppose $G$ contains a cycle:

If $G$ has a cycle, removing any edge in the cycle would still leave $G$ connected (because the cycle provides an alternate path between the vertices). This operation would result in a graph with $n$ vertices and $n-2$ edges, contradicting the fact that $G$ has exactly $n-1$ edges. Therefore, $G$ cannot contain a cycle.

Thus, $G$ is acyclic.

---

Step 3: The edge count property of a tree.

By definition, a tree with $n$ vertices has exactly $n-1$ edges. The graph $G$ satisfies this property since it is given that $G$ has $n-1$ edges.

---

Conclusion:

Since $G$ is connected, has no cycles, and has $n-1$ edges with $n$ vertices, $G$ satisfies all the properties of a tree. Therefore, $G$ is a tree.

---

Relation to Spanning Tree:

A spanning tree of $G$ is a subgraph that is a tree and connects all vertices. In this case, since $G$ is already connected and acyclic with the correct number of edges, $G$ itself is its spanning tree. Thus, $G$ must be a tree.

---

Let me know if you need further clarification or have any additional questions!

Related Questions:

1. How do you verify if a graph is a tree in practice?
2. Can a graph with $n-1$ edges and $n$ vertices be disconnected?
3. What happens if $G$ has $n-1$ edges but is not connected?
4. How does the edge count of a tree relate to its spanning tree property?
5. Can there be multiple spanning trees for a given connected graph?

Tip: Always verify both connectivity and absence of cycles to confirm a graph is a tree.