# If we construct a tree of all paths leading out of some root node, is that tree necessarily unique?

## Introduction

Our goal is to prove whether or not something called a "path tree" is unique for any directed graph $$G$$.

## Informal definition of Path Tree

Pick a digraph, any digraph.

Designate an arbitrary node in the digraph to be a root node.

A path tree for that digraph is rooted at the same root node.

Also, each node in digraph $$G$$ appears in the path-tree many times.

Specifically, the exact number of times a node $$x$$ from digraph $$G$$ is duplicated in tree $$T$$ is equal to the number of paths from the root node to node $$x$$ in graph $$G$$.

## Formal definition of Path Tree

A tree is any directed graph $$T$$ such that:

• the tree has exactly one root node
• the tree has zero or more branch nodes
• the tree has zero or more leaf nodes.
A “root node” is any node $$r$$ which has zero incoming edges and one outgoing edge. That is, $$\forall r \in VS(T)$$, $$r$$ is a root node if and only if $$\begin{Bmatrix}V \in VS(T): (V, r) \in AS(T) \end{Bmatrix} = Ø$$ and $$\exists X \in \begin{Bmatrix}V \in VS(T): (r, V) \in AS(T) \end{Bmatrix}$$ and $$\forall X, Y \in \begin{Bmatrix}V \in VS(T): (r, V) \in AS(T) \end{Bmatrix}$$, $$X = Y$$ .
It should be obvious what branch nodes are.
We define leaf nodes to be any nodes which have exactly one incoming edge and zero outgoing edges.

### Formal Definition of Path Tree

Let $$G$$ be a directed graph with vertex set $$VS(G)$$ and arc-set $$AS(G)$$.
For example, maybe $$VS(G) =\begin{Bmatrix} 1, 2, 3, 4 \end{Bmatrix}$$ and $$AS(G) =\begin{Bmatrix} (1, 2), (2, 3), (2, 4), (4, 4) (3, 2), (3, 3)\end{Bmatrix}$$ Note that we allow $$G$$ to have self-loops $$\begin{pmatrix}(x,x)\in AS \end{pmatrix}$$ Let $$r$$ be a node in digraph $$G$$.

a “Path Tree” of digraph $$G$$ rooted at node $$r \in VS(G)$$ is defined to be a tree $$T$$ such that there exists a mapping $$\mathcal{toG}$$ from the vertex set of tree $$T$$ to the vertex set of digraph $$G$$ such that all of the following are true:

• There exists a unique tree-node $$r^{\prime}$$ such that $$\mathcal{toG}(r^{\prime}) = r$$
• $$\forall V \in VS(T)$$, $$1 \leq \begin{vmatrix} \begin{Bmatrix} W \in VS(G): \mathcal{toG}(V) = W \end{Bmatrix} \end{vmatrix}$$ and $$\begin{vmatrix} \begin{Bmatrix} W \in VS(G): \mathcal{toG}(V) = W \end{Bmatrix} \end{vmatrix}$$ is equal to the number of distinct paths from $$r = \mathcal{toG}(r^{\prime})$$ to $$\mathcal{toG}(V)$$ in directed graph $$G$$. The paths are not necessarily disjoint from other paths, but nodes inside of a path are guaranteed to be distinct from other nodes inside of the same path.

# Re-stating the Question

Is the path-tree associated with rooted-digraph guaranteed to be unique for that choice of root and digraph?

### Note

What I call a "path tree" is like a spanning tree in many ways, except that nodes get repeated.

Given a rooted digraph $$G$$, just define the vertices of its path tree to be the finite paths in $$G$$ which start at the root, and let there be a directed edge in the path tree from a path $$p_0$$ in $$G$$ to a path $$p_1$$ in $$G$$ if $$p_1$$ is obtained from $$p_0$$ by adding one edge at the end.
This defines a directed graph, and it is easily seen that each vertex can be reached from the vertex corresponding to the path of length $$0$$ in $$G$$ by exactly one path, which corresponds to the finite sequence of initial parts of the corresponding path in $$G$$.