  The edges of the characteristic imset polytope, $\operatorname{CIM}_p$, were
recently shown to have strong connections to causal discovery as many
algorithms could be interpreted as greedy restricted edge-walks, even though
only a strict subset of the edges are known. To better understand the general
edge structure of the polytope we describe the edge structure of faces with a
clear combinatorial interpretation: for any undirected graph $G$ we have the
face $\operatorname{CIM}_G$, the convex hull of the characteristic imsets of
DAGs with skeleton $G$. We give a full edge-description of
$\operatorname{CIM}_G$ when $G$ is a tree, leading to interesting connections
to other polytopes. In particular the well-studied stable set polytope can be
recovered as a face of $\operatorname{CIM}_G$ when $G$ is a tree. Building on
this connection we are also able to give a description of all edges of
$\operatorname{CIM}_G$ when $G$ is a cycle, suggesting possible inroads for
generalization. We then introduce an algorithm for learning directed trees from
data, utilizing our newly discovered edges, that outperforms classical methods
on simulated Gaussian data.
