  This note presents several results in graph theory inspired by the author's
work in the proof theory of linear logic; these results are purely
combinatorial and do not involve logic.
  We show that trails avoiding forbidden transitions, properly arc-colored
directed trails and rainbow paths for complete multipartite color classes can
be found in linear time, whereas finding rainbow paths is NP-complete for any
other restriction on color classes. For the tractable cases, we also state new
structural properties equivalent to Kotzig's theorem on the existence of
bridges in unique perfect matchings.
  Another result on graphs equipped with unique perfect matchings that we prove
here is the combinatorial counterpart of a theorem due to Bellin in linear
logic: a connection between blossoms and bridge deletion orders.
