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

Question

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.

Answer 1

I understand your question as asking how to properly define the path tree that you have in mind. You do not say much about the edges of the path tree, so I have to guess what your intention is.

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$.