How can i prove that any tree contains a matching of size |InternalNodes|/2? Thanks in advance
You can prove the following stronger claim by induction:
Given a rooted tree containing more than one vertex, there is a matching which covers all non-leaf nodes.
The proof is quite simple – we match the root to an arbitrary child, remove the edge, and recurse on the remaining rooted trees. Each remaining tree in which the root is a non-leaf in the original tree will contain more than one vertex, and so the induction hypothesis applies.
I'll let you come up with the details.