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

alternative-proofdiscrete mathematicsgraph theorysolution-verificationtrees

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.

Best Answer

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.

Related Question