Let \(G(V,E,\gamma)\) be an undirected graph. The following propositions are equivalent:
\((1)\) \(G\) is a tree. \((2)\) \(G\) contains no cycle, and every supergraph \(S\) of \(G\) with the same set of vertices and an extended set of edges does contain a cycle. (\(G\) is "maximal acyclic").
\((3)\) For every pair of vertices \(u,v\in V\) there is exactly one path \(P^k:=x_0x_1\ldots x_{k-1}x_k\) in \(G\) with \(x_0=u\) and \(x_k=v\).
\((4)\) \(G\) is connected and the removal of any edge leaves \(G\) disconnected (\(G\) is "minimal connected").
\((5)\) \(G\) is connected and \(|E|=|V|-1\).
\((6)\) \(G\) contains no cycle and \(|E|=|V|-1\).
Proofs: 1
