There exists a unique path linking every two vertices in a tree $T$

I've come up with what feels like a really convoluted proof for a fairly simple theorem. There are a few points I'd like to improve upon:

1. I dislike using the physical language of "following" a path -- it feels more like an appeal to intuition than something that belongs in a formal proof. Can you suggest an alternate way of framing this?
2. I'm not entirely convinced by my own proof -- in part (I), for example, how do we know for sure that "following" (ugh, I did it again! :)) $$P_1 \cup P_2$$ will lead to a vertex in $$P_1 \cap P_1 \triangle P_2$$? How do I know that "following" $$P_1 \cap P_1 \triangle P_2$$ will lead to $$P_2 \cap P_1 \triangle P_2$$?
3. Is this proof salveageable, or are there any fatal assumptions made along the way?
4. Can you suggest a simpler proof?

To clarify notation:

By a graph I mean a pair $$(V, E)$$ with $$V$$ a set of elements called vertices, and $$E = \{ \{v_1, v_2\} : v_1, v_2 \in V\}$$. I take a path to be a nonempty graph with $$E = \{ \{ v_0, v_1\}, \{ v_1, v_2 \}, ..., \{v_{k-1}, v_k\}\}$$ where the $$v_i$$ are distinct.

The set theoretic operations I define as being applied componentwise to the elements of $$G$$ -- so $$G_1 \cap G_2 = (V_{G_1} \cap V_{G_2}, E_{G_1} \cap E_{G_2})$$. I take this notation mostly from Diestel (maybe except for the abuse of the notation for set theoretic operations).

Theorem There exists a unique path linking every two vertices in a tree $$T$$

Proof Existence follows from the definition of a tree (a connected acyclic graph).

We show uniqueness as follows: let $$P_1$$ and $$P_2$$ be paths linking vertices $$x_0, x_k \in T$$ with $$P_1 \neq P_2$$.

Take the symmetric difference $$P_1 \triangle P_2$$. Note that $$P_1 \triangle P_2$$ must be nonempty, since $$P_1 \neq P_2$$. Further, $$P_1 \cap (P_1 \triangle P_2) \neq \emptyset$$ and $$P_2 \cap (P_1 \triangle P_2) \neq \emptyset$$ (otherwise we would have, for example, $$P_1 \subset P_2$$, which is impossible since by hypothesis both paths link $$x_0$$ and $$x_k$$).

If $$P_1 \cap P_1 \triangle P_2 = P_1$$ and $$P_2 \cap P_1 \triangle P_2 = P_2$$ (if one of these is true, both are true), then we have a cycle with $$P_1 \cup P_2$$.

Otherwise, follow $$P_1 \cup P_2$$ until we arrive at a vertex of $$P_1 \triangle P_2$$.

(I) Follow $$P_1 \cup P_2$$ until we arrive at a vertex $$v$$ in $$P_1 \triangle P_2$$. This vertex is adjacent to vertices in both $$P_1 \cap P_1 \triangle P_2$$ and $$P_2 \cap P_1 \triangle P_2$$. Then we can follow $$P_1 \cap P_1 \triangle P_2$$ until we reach a vertex in $$P_2 \cap P_1 \triangle P_2$$, and follow $$P_2 \cap P_1 \triangle P_2$$ back to $$v$$.

Then a cycle exists, contradicting our hypothesis that $$P_1 \neq P_2$$. Then $$P_1 = P_2$$, and for every pair of points $$x_0, x_k$$ in a tree there exists a unique 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.

• Thanks so much for this -- I clarified the notation in my post. That said, I think my notation is cumbersome compared to yours and a part of what made this so difficult. I appreciate the alternate proof
– Hugo
Commented Oct 23, 2020 at 10:38
• @Hugo I think my notation is closer to most people's intuitive understanding of a path, while still remaining rigorous enough so that it is obvious that it can be written in a strictly formal way. My proof isn't really all that different to yours, the idea is the same, but the lower level of abstraction makes it more clear.
– 5xum
Commented Oct 23, 2020 at 10:50
• As long as we're being rigorous and very careful, please say "for all $i$, $p_i$ is adjacent to $p_{i+1}$" because "connected" is ambiguous. (It could simply mean "in the same connected component.) Commented Oct 23, 2020 at 13:09
• @MishaLavrov That one got lost in translation, I guess.
– 5xum
Commented Oct 23, 2020 at 13:38