  We study {\em breadth-first search (BFS)} spanning trees, and address the
problem of designing a sparse {\em fault-tolerant} BFS structure, or {\em
FT-BFS } for short, resilient to the failure of up to two edges in the given
undirected unweighted graph $G$, i.e., a sparse subgraph $H$ of $G$ such that
subsequent to the failure of up to two edges, the surviving part $H'$ of $H$
still contains a BFS spanning tree for (the surviving part of) $G$. FT-BFS
structures, as well as the related notion of replacement paths, have been
studied so far for the restricted case of a single failure. It has been noted
widely that when concerning shortest-paths in a variety of contexts, there is a
sharp qualitative difference between a single failure and two or more failures.
  Our main results are as follows. We present an algorithm that for every
$n$-vertex unweighted undirected graph $G$ and source node $s$ constructs a
(two edge failure) FT-BFS structure rooted at $s$ with $O(n^{5/3})$ edges. To
provide a useful theory of shortest paths avoiding 2 edges failures, we take a
principled approach to classifying the arrangement these paths. We believe that
the structural analysis provided in this paper may decrease the barrier for
understanding the general case of $f\geq 2$ faults and pave the way to the
future design of $f$-fault resilient structures for $f \geq 2$. We also provide
a matching lower bound, which in fact holds for the general case of $f \geq 1$
and multiple sources $S \subseteq V$. It shows that for every $f\geq 1$, and
integer $1 \leq \sigma \leq n$, there exist $n$-vertex graphs with a source set
$S \subseteq V$ of cardinality $\sigma$ for which any FT-BFS structure rooted
at each $s \in S$, resilient to up to $f$-edge faults has
$\Omega(\sigma^{1/(f+1)} \cdot n^{2-1/(f+1)})$ edges.
