I'm stuck on this problem, posting my progress so far below. I've looked at similar questions here and here, but neither seem to directly prove the predicate by induction, with a base case followed by the inductive step.
Solution(?):
Let P(n) be the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges).
Base case (n=1):
P(1): (n=1, any tree with 1 vertice has 0 edges). A tree G is a connected graph with no cycles of length at least three. An edge E is a two-element subset of the set of all vertices V of G. In the base case, V contains one vertice. Thus there are zero two-element subsets of V, or zero edges, in G.
Inductive Step:
For every n>0, P(n) => P(n+1).
For P(n+1), where n>0 in G, n+1 vertices will form exactly n edges. All vertices are of degree 1, which means there is exactly one less edge than vertice (one edge per vertice, excluding the root vertice). Thus, any tree with n vertices will have exactly n-1 edges.
Assume P(n) is true. Then, we want to prove that the graph G, for P(n+1), has n edges.
G contains no cycles of length at least three. Thus, G must contain only one region, meaning that the edges in G do not form any regions. This means that G must contain at least one leaf (vertex with degree of 1).
Obtain a graph G' by removing one leaf from G. Because a leaf is a vertex of 1, by the definition of vertex degree, the leaf is connected to exactly one edge. Thus, removing the leaf will remove one vertex and one edge from G, to create G'. This means that for all n, n>=1, any tree with (n+1) vertices will have ((n+1)-1). or n, edges.
We have proven that the case base P(1) is true, and assuming that P(n) is true, we see that the statement remains true for n => n+1. Thus, the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges) is true by induction.
Assume P(n) is true. Then, we want to prove that the graph G, for P(n+1), has n edges.
G contains no cycles of length at least three. Thus, G must contain only one region, meaning that the edges in G do not form any regions. This means that G must contain at least one leaf (vertex with degree of 1).
Remove a leaf l from G to obtain a tree G′ with n vertices. Then, G' has n−1 edges, by the inductive hypothesis. The addition of l to G′ produces a graph with n+1 vertices and n edges, since l has degree 1.
P(1) is true, and for every n>0, P(n) => P(n+1). Thus, the predicate must be true.
I'm not exactly sure how to proceed for the inductive step., or if I doing it correctly. Any hints, or confirmation that I'm going in the right direction would be greatly appreciated.
