  We consider a graph with colored edges. A trail (vertices may repeat but not
edges) is called \emph{alternating} when successive edges have different
colors. Given a set of vertices called \emph{terminals}, the \emph{alternating
reachability} problem is to find an alternating trail connecting distinct
terminals, if one exists. A special case with two colors is searching for an
augmenting path with respect to a given matching. In another special case with
two colors red and blue, the \emph{alternating cone} is defined as the set of
assignments of nonnegative weights to the edges such that at each vertex, the
total red weight equals the total blue weight; in a companion paper we showed
how the search for an integral weight vector within a given box in the
alternating cone can be reduced to the alternating reachability problem in a
2-colored graph. We define an obstacle, called a \emph{Tutte set}, to the
existence of an alternating trail connecting distinct terminals in a colored
graph, and give a polynomial-time algorithm, generalizing the blossom algorithm
of Edmonds, that finds either an alternating trail connecting distinct
terminals or a Tutte set. We use Tutte sets to show that an an edge-colored
bridgeless graph where each vertex has incident edges of at least two different
colors has a closed alternating trail. A special case with two colors one of
which forms a matching yields a combinatorial result of Giles and Seymour. We
show that in a 2-colored graph, the cone generated by the characteristic
vectors of closed alternating trails is the intersection of the alternating
cone with the cone generated by the characteristic vectors of cycles in the
underlying graph.
