Trees path

Let $\mathcal{G} = (\mathcal{N}, \mathcal{E})$ be an undirected tree (graph $G$ is undirected, connected, and has $|\mathcal{N}|=|\mathcal{E}| + 1$ if we count edges $(v, w)$ and $(w, v)$ as the same edge). Let $m, n \in \mathcal{N}$. We say that the distance between $m$ and $n$, denoted by dist(m,n), is the length of the shortest path between $m$ and $n$.

P1.1

Show that $\text{dist}(m, n) = \text{dist}(n, m)$

An undirected tree $\mathcal{G}$ has the following properties:

1. $\mathcal{G}$ is connected and acyclic
2. A tree with $n$ nodes has $n-1$ edges
3. In a tree, there is a unique path between any two vertices.

Let $m$ and $n$ be two arbitrary vertices in the $\mathcal{G}$. There exists a unique path $P$ from $m$ to $n$.

Let the vertices along the path $P$ be: $m, v_{1}, v_{2}, \dots, v_k, n$. The length of path is $k+1$, which is the number of edges

Let the vertices along the path $P^{'}$ be: $n, v_k, \dots, v_2, v_1, m$. Since $\mathcal{G}$ is an undirected graph, each edge $(v_i, v_{i+1})$ in $P$ corresponds to the same edge $(v_{i+1}, v_i)$ in $P^{'}$. Therefore, length of path $P^{'}$ is also $k+1$

dist(m, n) denotes the shortest path from m to n, and dist(n, m) denotes the shortest path from n to m. Since there is one unique path between m and n in the tree, both $P$ and $P^{'}$ are shortest paths between m and n, with length $k+1$

Therefore $\text{dist}(m, n) = \text{dist}(n, m)$ $\square$

P1.2

Prove that there is a unique path without repeated nodes and edges from node $m$ to node $n$ with length dist(m,n)

Since $\mathcal{G}$ is an undirected tree, there is a unique path between any two vertices. Let $m$ and $n$ be two arbitrary vertices in the $\mathcal{G}$. There exists a simple path $P$ from $m$ to $n$.

Suppose there are two different simple paths connecting $m$ and $n$:

where $j \neq k$. Since the paths are different and since $P_2$ is a simple path, $P_1$ must contain an edge that isn’t in $P_2$

Let $j \ge 1$ the first index for which the edge $\{ u_{j-1}, u_j \}$ of $P_1$ is not in $P_2$. Then $u_{j-1} = v_{j-1}$.

Let $u_k$ be the first vertex in path $P_1$ after $u_{j-1}$ (that is $k \geq j$) that is in the path $P_2$. Then $u_k = v_l$ for some $l \geq j$

We now have two simple path, $Q_1: u_{j-1}, \dots, u_k$ using edges from $P_1$ and $Q_2 : v_{j-1}, \dots, v_l$ using edges from $P_2$, between $u_{j-1} = v_{j-1}$ and $u_k = v_l$.

The path $Q_1$ and $Q_2$ have no vertices, edges in common, thus the path from $u_{j-1}$ to $u_k$ along $Q_1$ followed by the path from $v_l$ to $v_{j-1}$ along the reverse of $Q_2$ is a cyclic in $T$, which contradicts the assumption that $T$ is a tree.

Thus, the path from $m$ to $n$ is unique simple path $\square$

P1.3

Prove the triangle inequality $\text{dist}(m, n) \leq \text{dist}(m, x) + \text{dist}(x, n)$

Let $m,n,x$ be three arbitrary vertices in the undirected tree $\mathcal{G}$a

There exists a simple unique path $P_1$ from $m$ to $x$ (length is $\text{dist}(m,x)$), a simple unique path $P_2$ from $x$ to $n$ (length is ).

Consider $P$ formed by concatenating $P_1$ and $P_2$. This is a path from $m$ to $n$ that passes through $x$ (length is $\text{dist}(m,x)+\text{dist}(x,n)$)

since $P$ denotes path from $m$ to $n$, and $\text{dist}(m,n)$ denotes the shortest path between $m$ and $n$, we have

P1.4

Provide an algorithm that computes the distance $d=\text{max}_{m,n \in N} \text{dist}(m,n)$ that is the maximum distance between any pair of nodes in $\mathcal{G}$ in $\mathcal{O}(|\mathcal{N}| + \mathcal{E})$