Here I have defined a tree in graph theory and proved it like that. and on the proof of 5. ⇒ 6.) my teacher gave me a comment that "where is proof of connectivity?" what does it mean and how is it?
A tree can be defined in a variety of ways as is shown in the following theorem: Theorem: The following statements are equivalent:
1. G is a tree.
2. There exists a unique path between every two vertices of G.
3. G does not hold any closed paths and for n > 2 every additional edge creates a closed path in G.
4. G is connected and contains no closed path.
5. G does not contain a closed path and e = n − 1.
6. G is connected and e = n − 1.
Proof:
1. ⇒ 2. ) There exists at least one path between u and v as G is connected. If there was a second path between u and v, any edge on this path (not belonging to the first path) could be removed without making G disconnected.
2. ⇒ 3. ) G cannot contain a closed path that holds the vertices u and v as these results in two paths between u and v. Let u′v′ ∉ E(G), i.e., u′v′ is an edge that is not a part of G, then adding u′v′ would create two paths between u′ and v′.
3. ⇒ 4. ) If G is not connected, we could take u and v such that they do not reside in the same component. Adding the edge uv would not create a closed path.
4. ⇒ 5. ) Apply induction on n (the case n = 1 is trivial). Let H = G − uv, where uv is an arbitrary edge in G. u and v have to belong to a different component of H (say, Hu and Hv ), otherwise G would hold a closed path containing u and v. For each of these components, criteria 4 is met, thus e = eHu + eHv + 1 = nHu + nHv − 1 = n − 1.
5. ⇒ 6. ) Assume G has k components (say, H1, H2, . . ., Hk ). For each component Hi we have eHi = nHi − 1, meaning that e = ∑i eHi = ∑i (nHi − 1) = n − k. Hence, k = 1.
6. ⇒ 1. ) Removing any edge makes G disconnected, because a graph with n vertices clearly needs at least n − 1 edges to be connected.
The proof $5\Rightarrow 6$ shows that $G$ consists only of one component ($k=1$) and so $G$ is connected.