Equivalent characterisations of a nonempty tree by unique paths, edge count, minimal connectivity and maximal acyclicity

If $G$ is a tree, connectedness supplies a path between each two vertices, and two distinct paths would contain a cycle. Thus condition 1 implies condition 2.

Under condition 2, $G$ is connected. Deleting any edge $uv$ leaves no $u$-$v$ path, because such a path together with $uv$ would give a second path in $G$. Thus condition 2 implies condition 5.

Suppose condition 5 holds. If $G$ contained a cycle, deleting one edge of that cycle would leave its endpoints joined around the rest of the cycle and would not disconnect $G$. Hence $G$ is acyclic and therefore is a tree. Thus condition 5 implies condition 1.

Condition 1 implies condition 3 by the tree edge count.

Under condition 3, suppose $G$ had a cycle. Repeatedly delete an edge from a cycle; each deletion preserves connectedness, and finiteness makes the process stop at a connected acyclic spanning graph $T$. At least one edge was deleted, so $\mathrm{\mid }E(T)\mathrm{\mid }<\mathrm{\mid }V(G)\mathrm{\mid }-1$, while the forest identity with one component gives $\mathrm{\mid }E(T)\mathrm{\mid }=\mathrm{\mid }V(G)\mathrm{\mid }-1$, a contradiction. Hence condition 3 implies condition 1.

Under condition 4, the forest identity gives $\mathrm{\mid }V\mathrm{\mid }=(\mathrm{\mid }V\mathrm{\mid }-1)+c$, so $c=1$ and $G$ is a tree. Conversely condition 1 implies condition 4 by definition and the tree edge count.

Condition 1 implies condition 6 by edge addition.

Under condition 6, if $G$ were disconnected, vertices in different components would be nonadjacent and adding an edge between them could create no cycle. Hence $G$ is connected, and its assumed acyclicity makes it a tree.

All six conditions are therefore equivalent.