Return to Answer

(This needs to be fixed:)

The trees produced by BFS can be characterized by the fact that each node is at minimal distance:

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

1. $T$ is a tree.

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

   a. For all vertices $w \in V: v \leq w$.

   b. For all vertices $w_1,w_2,w_3 \in V$, if $\{w_1,w_3\}$ and $\{w_2,w_3\}$ are edges of $G$ and $w_1 < w_2$, then $\{w_1,w_2\}$ is an edge of $T$.

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.

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.

(This needs to be fixed:)

The trees produced by BFS can be characterized by the fact that each node is at minimal distance:

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

1. $T$ is a tree.
2. For every vertex $w \in V$, the distance from $v$ to $w$ in $T$ is equal to the distance between $v$ and $w$ in $G$.
3. For all vertices $w_1, w_2, w_3 \in V$, if $\{w_1,w_2\}$ and $\{w_1,w_3\}$ are edges of $G$ and QQQQQQQQQ

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

By the way, why not use undirected trees?.

(This needs to be fixed:)

The trees produced by BFS can be characterized by the fact that each node is at minimal distance:

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

1. $T$ is a tree.

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

   a. For all vertices $w \in V: v \leq w$.

   b. For all vertices $w_1,w_2,w_3 \in V$, if $\{w_1,w_3\}$ and $\{w_2,w_3\}$ are edges of $G$ and $w_1 < w_2$, then $\{w_1,w_2\}$ is an edge of $T$.

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.

(This needs to be fixed:)

The trees produced by BFS can be characterized by the fact that each node is at minimal distance:

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. For every vertex $w \in V$, the distance from $v$ to $w$ in the tree is equal to the distance between $v$ and $w$ in $G$.

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

By the way, why not use undirected trees?.

(This needs to be fixed:)

The trees produced by BFS can be characterized by the fact that each node is at minimal distance:

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

1. $T$ is a tree.
2. For every vertex $w \in V$, the distance from $v$ to $w$ in $T$ is equal to the distance between $v$ and $w$ in $G$.
3. For all vertices $w_1, w_2, w_3 \in V$, if $\{w_1,w_2\}$ and $\{w_1,w_3\}$ are edges of $G$ and QQQQQQQQQ

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

By the way, why not use undirected trees?.