Which two of the following are equivalent for an undirected graph \(G\) ? (i)…

Concept

For an undirected graph G on n vertices, being a tree has several well-known equivalent characterizations: G is connected and contains no cycles; G is acyclic and has exactly (n - 1) edges; G is connected and has exactly (n - 1) edges; and there is a unique path between every pair of vertices. Any one of these conditions holding forces every other one to hold as well.

Application

1. Statement (ii) says only that there is at least one path between any two vertices of G - this is exactly the definition of connectedness and says nothing about cycles. A connected graph that also contains a cycle (for example, a simple triangle) still satisfies (ii), so (ii) alone does not force G to be a tree.

2. Statement (iii) says G contains no cycles and has (n - 1) edges. This is precisely the acyclic-plus-(n - 1)-edges characterization above, which the theorem confirms is equivalent to G being a tree.

3. Statement (iv) says G has n edges. Every equivalent characterization of a tree requires exactly (n - 1) edges, so an edge count of n is inconsistent with G being a tree rather than equivalent to it.

4. Since only statement (iii) matches a valid equivalent characterization of statement (i), the two statements that are equivalent to each other are (i) and (iii).

Cross-check

Take n = 4. A path graph on 4 vertices has 3 = (n - 1) edges and no cycles, so it is a tree - consistent with (iii). A 4-cycle on the same 4 vertices is connected (it satisfies (ii)) and has 4 = n edges (it satisfies (iv)), yet it contains a cycle and is not a tree. This confirms that (ii) alone and (iv) alone fail to characterize a tree, while (iii) - no cycles and (n - 1) edges - does. So (i) and (iii) are the equivalent pair.