# Some part of proof of Tree are not clear for me in this induction.

Exactly the last part of this which I made it bold and says it is obvious is not obvious for me, can you explain it to me?

Theorem: The following conditions are all equivalent for a graph G = (V, E): [1]

(i) G is a tree. (ii) (Path uniqueness) For every two vertices x, y ∈ V , there exists exactly one path from x to y. (iii) (Minimal connected graph) The graph G is connected, and deleting any of its edges gives rise to a disconnected graph. (iv) (Maximal graph without cycles) The graph G contains no cycle, and any graph arising from G by adding an edge already contains a cycle.

(v) (Euler’s formula) G is connected and |V | = |E| + 1

Lemma (Tree-growing lemma). The following two statements are equivalent for a graph G and its end-vertex v: (i) G is a tree (ii) G − v is a tree.

Proof of Lemma: First we prove the implication (i)⇒ (ii). The graph G is a tree, and we want to prove that G − v is a tree as well. Consider two vertices x, y of G−v. Since G is connected, x and y are connected by a path in G. This path cannot contain a vertex of degree 1 (he degree of a vertex of a graph is the number of edges that are incident to the vertex) different from both x and y, and so it doesn’t contain v. Therefore it is completely contained in G − v, and we conclude that G − v is connected. Since G has no cycle, obviously G − v cannot contain a cycle, and thus it is a tree. It remains to prove the implication (ii)⇒ (i). Let G−v be a tree. By adding the end-vertex v back to it, no cycle can be created. We must also check the connectedness of G: any two vertices distinct from v were connected already in G − v, and a path to v from any other vertex x is obtained by considering the (single) neighbor v′of v in G, connecting it to x by a path in G − v, and extending this path by the edge {v′, v}.

This lemma allows us to reduce a given tree to smaller and smaller trees by removing end-vertices successively. Now we are going to apply this device.

Proof of Theorem:

We prove that each of the statements (ii)–(v) is equivalent to (i). This, of course, proves the mutual equivalence of all the statements. The proofs go by induction on the number of vertices of G using the tree-growing lemma As for the induction basis, we note that all the statements are valid for the graph with a single vertex.

First we that (i) implies all of (ii)–(v). To this end, let G be a tree with at least 2 vertices, let v be one of its end-vertices, and let v′ be the single neighbor of v in G. Suppose that the graph G−v already satisfies (ii)–(v); this is our inductive hypothesis.

In this situation, the validity of (ii), (iii), and (v) for G can be considered obvious