Are there theorem dual to Tarjan's theorem for breath first search?

Question

In "Depth-First Search and Linear Graph Algorithms" Tarjan proposed following theorem as the foundation of depth-first search (rephrase a little bit):

Let $G=(V,E)$ be a connected (undirected) graph and $v\in V$ be a vertex, then there is a directed tree as subgraph of $G$ such that:

1. $v$ is the root of $G$.
2. Any edge $(p,q) \in E$ is non-crossing, namely $p$ is an ancestor of $q$, or $q$ is an ancestor of $p$

And there is a "one-word proof": DFS (depth-first search). Moreover, Tarjan proved that all such trees are generated by DFS. My question is, are there theorem that could characterize all trees generated by breadth-first search?

Answer 1

BFS trees are a standard notion like DFS trees. See for example Chapter 22 of Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein (aka. CLRS). Notably the following exercise (emphasis mine):

A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search into the same four categories.

a. Prove that in a breadth-first search of an undirected graph, the following properties hold:

• There are no back edges and no forward edges.
• For each tree edge $(u,v)$, we have $v.d=u.d+1$.
• For each cross edge $(u,v)$, we have $v.d=u.d$ or $v.d=u.d+1$.

b. Prove that in a breadth-first search of a directed graph, the following properties hold:

• There are no forward edges.
• For each tree edge $(u,v)$, we have $v.d=u.d+1$.
• For each cross edge $(u,v)$, we have $v.d≤u.d+1$.
• For each back edge $(u,v)$, we have $0≤v.d≤u.d$.

Answer 2

This is an attempt; please check.

Let $G=(V,E)$ be a connected (undirected) graph and $v\in V$ be a vertex, then consider all subgraphs $T=(V,F)$ of $G$ such that:

1. For each vertex $w\in V$, its distance to $v$ is the same in $G$ and $T$.

2. There is a total order $<$ on $V$ such that:

   a. For each vertex $w \in V: v \leq w$.

   b. An edge $\{ w,x \} \in E$ is in $F$ if and only if there is no edge $\{ y,x \} \in E$ with $y < w$.

The trees produced by BFS should be exactly the trees satisfying this condition; the order is a BFS order. A proof should be analogous to a proof of Tarjan's theorem.