Consider a directed graph D=(V, E \subseteq V \times V). A set T \subseteq E is an arborescence (oriented forest) if:

T does not contain a cycle (ignoring directions of edges).

Every vertex in V has at most one incoming edge.

An arborescence T with |T|=n-1 will have one incoming edge incident on each node except one. If we denote this special node as root, this is an oriented spanning tree as shown in the figure.

Consider the underlying undirected graph G_D = (V,E) associated with D (this is the graph obtained by “erasing the arrows” in D). Consider the universe given by E. Suggest two matroids {\mathcal M}_1 and {\mathcal M}_2 for which set of arborescences is given by the sets independent in both {\mathcal M}_1 and {\mathcal M}_2.

Hint: these are both matroids seen in class. Further, you might find it useful to partition E into |V| many parts as follows — the part P_v contains all edges that are incoming arcs for the vertex v in D. Can you define a matroid based on this partition?

Describe {\mathcal M}_1 and {\mathcal M}_2.