Prove that a connected graph G with n vertices and n-1 edges is a tree.

To prove that a connected graph G with n vertices and n-1 edges is a tree, we can follow these steps:

Step 1: Recall the definition of a tree. A tree is an undirected graph that is connected and acyclic, meaning it has no cycles.

Step 2: Given that G is a connected graph with n vertices and n-1 edges, we need to show that it satisfies the properties of a tree.

Step 3: Start by assuming that G is not a tree. This means that G either has cycles or is not connected.

Step 4: If G has cycles, then it cannot be acyclic, contradicting the definition of a tree. Therefore, G cannot have cycles.

Step 5: Now, let's consider the case where G is not connected. If G is not connected, it means that there are two or more disconnected components in the graph.

Step 6: Since G has n vertices, it must have at least n-1 edges to be connected. However, if G is not connected, it means that it has fewer than n-1 edges.

Step 7: This contradicts the given information that G has n-1 edges. Therefore, G must be connected.

Step 8: We have shown that G is both connected and acyclic, satisfying the properties of a tree.

Step 9: Hence, we can conclude that a connected graph G with n vertices and n-1 edges is indeed a tree.