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.