A [[Trees (graph theory)]] # Proofs that trees on $n$ vertices have $n-1$ edges ###### Proof by induction Proceed by induction on n and use [[Finite tree with at least two vertices has a leaf]]. ###### Bijective proof Pick a vertex $v$ as a 'root' and direct all edges away from $v$. This yields a bijection between the non-root vertices and the edges by matching each edge with the vertex it points at ([^1], p. 89). Thus $|V|=|E|-1$. # Proof of Converse # References  [^1]: Springer-Verlag GmbH Germany, part of Springer Nature 2018 M. Aigner, G. M. Ziegler, Proofs from THE BOOK, https://doi.org/10.1007/978-3-662-57265-8_13