
The first concerns the structure of unique perfect matchings, in
particular their inductive or hereditary characterization
suggested by Kotzig's theorem. We relate this with the
blossoms [1]} which appear in combinatorial
matching algorithms. This was discovered by directly transposing a theorem on
proof nets, due to Bellin [2]}, using the reductions
defined in our previous work [3]}; it turned out that a
notion of dependency investigated by logicians corresponded exactly
to blossoms. The result already appeared in the conference version of the
latter paper, but we present it here in a stand-alone way for a broader
audience of graph theorists, using the direct proof
from [3]}.

The second is a study of some constrained path-finding problems, which
covers the results that we have previously announced at the
CTW'18Cologne-Twente Workshop on Graphs and Combinatorial
Optimization 2018. workshop. We show, for most of these studied problems,
that they belong to the aforementioned family. This leads to algorithms to
solve them and structure from acyclicity properties. In one case, we
establish a dichotomy theorem between a tractable case – which is
indeed equivalent to augmenting paths in matchings – and a NP-complete case.
A key ingredient in all of those results is a simple edge-colored line
graph construction; here the input of proof nets is that this construction
was discovered by dissecting Retoré's aforementioned
work [5]}, in which it implicitly occurs. We also
prove, at the end of the paper, a simple NP-completeness result that does not
rely on this construction.

