Prove by induction the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges). 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. 
 A: For $P(n+1)$, you clain "all vertices are of degree $1$". That is not true in trees at all. Also, you need to prove $P(n+1)$, while you have only "proven" $P(n)$.
What you must do is assume that $P(n)$ is true, i.e. "all trees with $n$ vertices have $n-1$" edges. Then, take any tree $G$ with $n+1$ vertices and prove it has $n$ edges.
To do that, here's a Hint:
Find one vertex of $G$ that has a degree of $1$ (a "leaf") and remove it.
A: We proceed by induction on $n$. When $n=1$ there exists only only tree, namely $K_1$, which has $0$ edges. Assume the result is true for every tree of order $n-1$ and size $n-2$. Let $T$ be a tree of order $n$ and size $m$. We know that every tree has at least two leaves. Let $v$ be a leaf. We also know that $T-v$ is a tree of order $n-1$ and by the induction hypothesis $T-v$ has size $n-2$. Thus $m=(n-2)+1=n-1$ and we can conclude that if $T$ is a tree of order $n$ and size $m$, then $m=n-1$.
A: Using structural induction, 
P(1) holds as a tree with 1 node has 0 edges.
Inductive hypothesis: Assume P(n) holds i.e., a tree with n nodes has n-1 edges.
To prove: P(n+1) i.e, a tree with n+1 nodes has n edges.
Now consider a tree T of n nodes. Let us try to add a new node to T to make a new tree T'.
In doing so, you can add exactly one edge from any one of the existing nodes in the tree T to the new node - because, if you added more than one edge to the new node (say from another existing node in the tree), then you would introduce a cycle - and it wouldn't be a tree anymore by definition (A tree is a connected graph with no cycles).
As a result, a our new tree T' of n+1 nodes has n-1+1 (=n) edges. This proves P(n+1).
As a result, we have P(1) and P(n) -> P(n+1) - which completes our proof for P(k).
A: BASE CASE:
  n = 1; vertices|V| = 1, edges|E| = (|V| - 1) = 0
set n = |V|
INDUCTIVE STEP:
  Assume true for n = k, k >= 1.
|E| = (k - 1)  ==  k = (|E| + 1)
Then, for n = (k + 1)
(k + 1) = |E| + 1,  |E| = ((k + 1) - 1)
(k + 1) = ((k + 1) - 1) + 1
(k + 1) = (k + 1)
True 
