Proof of equivalence of parse-trees and derivations
Theorem.
Let $G = (V, T, P, S)$ be a Context-free Grammar. Then $\forall A \in V, A \rightarrow^* \alpha \Leftrightarrow \exists$ a parse-tree $T'$ rooted at node $A$ with yield $\alpha \in (V \cup T)^*$.

Meanings of symbols:


$V$ is the set of non-terminals
$T$ is the set of terminals
$P$ is the set of productions
$S \in V$ is a designated start symbol.


A parse-tree $T'$ for a derivation is defined as follows:  


The root is labeled with a symbol $\in V$
If $T'$ has a node labeled $A$ whose children are labeled $X_1, X_2, \dots, X_n$ such that $X_i$ is to the left of $X_j$ for all $i \lt j$, then $A \rightarrow X_1X_2\dots X_n$ is a production $\in P$.


proof. We prove $\forall A \in V, A \rightarrow^* \alpha \Rightarrow\exists$ a parse-tree $T'$ rooted at $A$ with yield $\alpha \in (V \cup T)^*$ and vice-versa. We will refer to a node with label $L$ as node $L$.

First we show the ($\Leftarrow$) part.

Assume there is a parse-tree $T'$ rooted at $A$ with yield $\alpha$. If the tree has $1$ internal node, then $A \rightarrow \alpha$ is a production in $P$ (by definition of a parse-tree). Since $A \rightarrow \alpha \Rightarrow A \rightarrow^* \alpha$, we are done.

Assume that the ($\Leftarrow$) part holds for all parse-trees with fewer than $n$ internal nodes (induction hypothesis). If the parse-tree has $n \gt 1$ internal nodes, let $X_i, i = 1, 2, \dots, m$ (be it a non-terminal or a terminal) denote the label of the $i^{th}$ child of the root-node $A$. Each of the $X_i$ nodes has fewer than $n$ nodes. By the induction hypothesis, each of the $X_i$ nodes is the root of a parse-tree with yield $x_i$. Knowing that all the descendants of $X_i$ are to the left of all of the descendants of $X_j$ for all $i &lt; j$, we can write $\alpha = x_1x_2\dots x_m$. $A \rightarrow X_1X_2\dots X_m$ is a production in $P$ and a derivation looks like:  $A \rightarrow X_1X_2\dots X_m \rightarrow^* x_1X_2\dots X_m \rightarrow^* \dots \rightarrow^* x_1x2\dots x_m = \alpha$.

Now we show the ($\Rightarrow$) part.

Assume $A \rightarrow^* \alpha$ for some $A \in V$. If $A \rightarrow \alpha$, then the tree in Fig. 1 is a parse-tree with yield $\alpha$ and we are done.

Assume that the ($\Rightarrow$) part holds for all derivations with fewer than $n$ steps (induction hypothesis). If $A \rightarrow^* \alpha$ is a derivation with $n$ steps, let $A \rightarrow X_1X_2\dots X_n$ be the first step in the derivation-chain. Let $V' = {X_1, X_2, \dots, X_n} \cap V$. Each of the elements of $V'$ derives a sub-string of $\alpha$ with fewer than $n$ steps. By the induction hypothesis, there is a parse-tree rooted at node $V'_i$ with yield $v'_i$. We form a parse tree rooted at $A$ with yield $\alpha$ as follows:


Add a root-node labeled with $A$
Add a link between $A$ and every node labeled with a symbol $\in V'$
Add a link between $A$ and every node labeled with a symbol $\in \{X_1, X_2, \dots, X_n\} \cap T$




This ends the proof.