Proposition: Equivalent Definitions of Trees

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

Proofs: 1 2 3

Thank you to the contributors under CC BY-SA 4.0!




  1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition