A tree is a connected graph containing no cycles. Let \(T\) be a tree with \(v\) vertices and \(e\) edges. We need to prove that:
We can manually check that, for a tree, the following are true:
If the above is not true, then there should exist a tree with some number of vertices that is not one more than the number of edges. Out of all the counterexamples, let's call the one with the smallest number of vertices \(T_1\). Assume that this tree has more than 2 vertices. Let the number of vertices of \(T_1\) be \(v_1\).
Since \(T_1\) is a tree, it should have atleast one "leaf vertex", or a vertex with degree one. Let \(T_2\) be the tree resulting from removing a leaf vertex from \(T_1\). Let \(v_2\) be the number of vertices of \(T_2\):
Since \(T_1\) is the smallest tree for which the stated proposition isn't true, then this means the proposition is true for \(T_2\). This means if \(v_2 = v_1 - 1\), then \(e_2 = v_1 - 2\) (where \(e_2\) is the number of edges of \(T_2\)). However, \(T_1\) has only one more edge than \(T_2\):
This means there is a contradition, because \(T_1\) satisfies the proposition.