Is this a valid weak induction proof on the number of branches in a tree? what would be a strong induction version?

The exercise goes as follows: prove by strong mathematical induction that for any tree $T$, if $n$ is the number of nodes and $m$ is the number of branches in $T$, then $n = m + 1$

I'm a beginner and haven't quite grasped the concept of strong induction so I tried my luck with weak induction first:

According to the property stated in the exercise then it must be the case that $m = n - 1$, so let $P(n) = n = (n - 1) + 1$ be the property we want to prove.

The base case is a tree with only one node and no branches so: $P(1) = 1 = (1 - 1) + 1$ which is true.

Let $k$ be any arbitrary positive integer to formulate the inductive hypothesis:
$P(k) = k = (k - 1) + 1$

Assuming the inductive hypothesis as true, let us prove the case for $k + 1$ to prove the theorem:
$P(k + 1) = (k + 1) = [(k + 1) - 1] + 1$

By the inductive hypothesis:
$P(k + 1) = [(k - 1) + 1] + 1 = [(k +1) - 1] + 1$

$ = P(k + 1) = k + 1 = k + 1$

Now my question is if this proof is correct in the first place since it seems a bit redundant (?) and how could I make this proof in a strong induction style. I know I'm supposed to assume that all cases up to $k$ are correct to do strong induction, but I only sort of understand it for sequences and this leaves me hanging a bit.

Answer

An important part of any induction proof is to be very clear what the proposition is!
In this case, P(n) is the proposition that a tree with $n$ nodes has $n-1$ branches.

Your proof that P(1) holds is fine. So we now wish to prove P(k+1).

There's no need to be wary of strong induction. It allows you to assume that P(i) is true for every $i\le k$ and not just that $P(k)$ is true.It gives you more to work with!

OK. So we have a tree with $k+1$ nodes and we know that our proposition holds for all trees with fewer nodes. We need to find some smaller trees that we can use.

Let's take a branch of our tree and remove it. Because we had a tree (which has no cycles) it will now be split into two smaller trees. Let's say that one has $a$ nodes and one $b$ nodes. Important - remember that $$a+b=k+1.$$

How many branches does the tree with $a$ nodes have? It must have $a-1$. The other small tree must have $b-1$.

See why we needed to use strong induction?

So, how many edges did our large tree have before we lopped a branch off? Can you see why it must have had $$(a-1)+(b-1)+1?$$
But this number of branches is $a+b-1=(k+1)-1=k$, just what we wanted!