Binary Tree, Prime Branches

For simplicity, we will denote the nodes with ordinal numbers as put in the image above right in the question. For instance, the left and right children of the root would be called the $2^{nd}$ and $3^{rd}$ nodes respectively.

Now since all the sums will definitely exceed $2$ , all the prime sums must be odd. Considering the shortest path, if $2^{nd}$ node is odd, the $5^{th}$ node must be odd; otherwise, the sum would even. Consequently, that means either $4^{th}$ or $7^{th}$ must be odd so that the sum is odd. In the end, four odd digits will be used, leaving only one odd left on the right wing. However, if the $3^{rd}$ or the $6^{th}$ node is odd, all other nodes will be even, and with root node of $1$ , the sums will be even. On the other hand, if the $8^{th}$ or the $9^{th}$ is odd, the sum on the other path will be even. Thus, the $2^{nd}$ node can't be odd.

Similarly, if $2^{nd}$ node is even, the $5^{th}$ node must be even. Thereby, that makes the pair of $4^{th}$ & $7^{th}$ both odd or both even. If the left wing has all even numbers, the right wing will have all odd numbers, yielding only even sums. Thus, we will have the pair of even $2^{nd}$ & $5^{th}$ nodes and the pair of odd $4^{th}$ & $7^{th}$ nodes. That leaves two odd and two even numbers to be used. Considering the $8^{th}$ & the $9^{th}$ nodes, they must be either both even or both odd as they have the same mother path. If they are both odd, the sums from root $1$ will result in even sums. Hence, we will have the pair of even $8^{th}$ & $9^{th}$ nodes and the pair of odd $3^{rd}$ & $6^{th}$ nodes. The image below concludes our proof for Odd and Even digits:

Considering the odd pairs, there are six possible combinations for the left and right wings: {(3+5),(7+9)}, {(3+7),(5+9)}, {(3+9),(7+5)}, {(5+7),(3+9)}, {(5+9),(3+7)}, {(7+9),(3+5)}. $$

First, let us consider the equal and interchangeable {(3+9),(7+5)} & {(5+7),(3+9)}:

Since $3+9+1 \equiv 7+5+1 \equiv 1 \pmod{3}$ , along all paths, we can not put a digit which equals to $2 \pmod{3}$ , namely $2$ & $8$ ; otherwise, the sum will be a multiple of three and not prime. Therefore, $2$ & $8$ can't be put in the $2^{nd}$ , $8^{th}$ , & $9^{th}$ , leaving only the $5^{th}$ node for two numbers, which impossible. Thus, this case is not applicable. $$

Second, for {(3+7),(5+9)}, $3+ 7+1 \equiv 2 \pmod{3}$ and $5+ 9+1 \equiv 0 \pmod{3}$ . Thus, $4$ can't be put in the $2^{nd}$ node while $6$ can't be put in either $8^{th}$ or $9^{th}$ node. That means $6$ is in $2^{nd}$ or $5^{th}$ node. However, since $6+2+1 = 9$ and $6+8+1 = 15$ , the left wing must have $6$ and $4$ , and since $4$ can't be put in the $2^{nd}$ node, $6$ is in the $2^{nd}$ node and $4$ the $5^{th}$ as show below:

However, the sums of $17$ are repeated, so this case is not applicable. $$

Third, for {(5+9),(3+7)}, similarly, due to modulus of three, $4$ can't be put in either $8^{th}$ or $9^{th}$ node while $6$ can't be put in the $2^{nd}$ node. If $4$ is in $2^{nd}$ node, $8$ can't be in the $8^{th}$ or $9^{th}$ node because $4+5+9+1 = 8+3+7+1=19$ , making the sums equal, but then if $8$ is in the $5^{th}$ node, the $4+8+1 = 1+3+7+2 =13$ , making it also not distinct, which will also yield the same results with $4$ in the $5^{th}$ and $8$ in the $2^{nd}$ node. That leaves us with $2$ in the $2^{nd}$ and $4$ in the $5^{th}$ node, but $1+2+5+9 = 1+3+7+6 = 17$ , which is also not satisfying. Thus, this case is also not applicable.

$$

Fourth, for {(7+9),(3+5)}, $1+7+9 \equiv 2 \pmod{3}$ and $1+3+5 \equiv 0 \pmod{3}$ , the $2^{nd}$ node can't have $4$ , and $6$ can't be put in either $8^{th}$ or $9^{th}$ node. That leaves us with one possibility: $6$ is in the $2^{nd}$ and $4$ in the $5^{th}$ node, as shown below.

Again $11$ is repeated. This is not the solution.

$$

Finally, for {(3+5),(7+9)}, similarly, with modulus of three, the $2^{nd}$ node can't have $6$ , and $4$ can't be put in either $8^{th}$ or $9^{th}$ node. Therefore, $4$ will be in either $2^{nd}$ or $5^{th}$ node while $6$ is in either $8^{th}$ or $9^{th}$ node.

Then if $8$ is in $8^{th}$ or $9^{th}$ node, $1+7+9+8 = 25$ , which is not prime, so $8$ is in either $2^{nd}$ or $5^{th}$ node. That leaves us with two final scenarios:

Only the right combination works, and this is the only possible method (with 8 permutations among the pairs) to yield four primes of $13, 17, 19, 23$ . This, thus, concludes our proof.