Tree (graph theory)

In graph theory, the following statements about a graph G with n vertices are equivalent:

1. G is connected and has no loops
2. G has no loops and, if an edge is added to G, then a loop is formed
3. G is connected and, if an edge is removed from G, then it becomes disconnected
4. G is connected and has n-1 edges
5. G has n-1 edges and no loops

Any of these five statements therefore serves as the definition of a tree. Usually, the first statement is preferred as the definition.