I think that the proof is easy assuming that there are at least two paths between any two nodes. If that is true then there must be a cycle somewhere. But if there is a cycle then this is not a tree, which is a contradiction. I feel like the step when i say that there must be a cycle if there is more than one path is kind of sloppy. It sounds like it is true but i am not sure about that. How do i make my proof a little bit more rigorous?
[Math] Prove that the path between two nodes is unique if the graph is a tree.
graph theory
Related Solutions
Another way of saying this: for some $k$, $1 \le k \le \lfloor n/2 \rfloor$, there is only one node at distance $k$ from $s$ (otherwise, counting $s$, $t$ and at least $2$ nodes at each $k$ you'd nave at least $2 + 2 \lfloor n/2 \rfloor > n$ vertices).
Every path from $s$ to $t$ must pass through a node at distance $k$ from $s$, so if you delete the only such node you no longer have such a path.
There are some things I don't like about this proof. One, you claim that $P_1\subset P_2$ is impossible since both paths link $x_0$ and $x_k$. But it's not obvious to see why the hypothesis makes it impossible for $P_1$ to be a "subset" of $P_2$.
But that's a minor thing. The main problem (connected to the one above) is the fact that a path is a sequence of vertices, not a set of vertices.
You are using a path as a set, but I don't think it's clear at all what $P_1\Delta P_2$ even means in the context of paths. What precisely, in your example, is $P_1$ anyway? What are the elements of it?
Anyway, I would suggest a simpler approach. One where a path $P$ is defined by a sequence of unique vertices $p_1,p_2,\dots p_n$ such that for all $i$, $p_i$ is adjacent to $p_{i+1}$ (i.e., there exists an edge $\{p_i, p_{i+1}\}\in E$). This is a perfectly fine rigorous definition.
Under this definition, take two paths, $P=(p_1,p_2,\dots p_n)$ and $Q=(q_1,q_2,\dots q_m)$ where $p_1=q_1=x_0$ and $p_2=q_2=x_k$.
Now, you can perform the following steps:
First, define $i_0$ as the first value of $i$ at which $p_i\neq q_i$.
You can show, from the premise that $P$ and $Q$ are different paths linking the same two vertices, that the number $i_0$ exists, and that it is not $1$.
Now, look at the sequence of vertices $$p_{i_0-1}, p_{i_0}, p_{i_0 + 1}, \dots p_{n}, q_{m}, q_{m-1}, \dots, q_{i_0 + 1}, q_{i_0}, q_{i_0-1}$$
Because you know that $p_{n}=q_m$ and $q_{i_0-1}=p_{i_0-1}$, you can show conclude that this sequence contains a nontrivial cycle, meaning you reached a contradiction.
Best Answer
If you have two distinct paths between two common nodes, then the paths may agree for a while beginning at the start node, and also agree for a while ending at the end node, but the point is that somewhere the two paths must diverge from each other and be disjoint (even if it's just for one node), and then later return to a common node. If this were not true, you would have the same path for both paths. This gives you your cycle. If you'd like, I can also provide a proof by induction, if you accept that a tree with $n$ nodes is always obtainable somehow by removing a leaf node from a tree with $n+1$ nodes.