# Spanning tree of a strongly connected directed graph.

Given a strongly connected directed graph $G=(V,E)$, and a node $r \in V$. Let $T_r$ be the set of spanning trees of $G$ with $r$ as root and all edges pointing to $r$. Is is it possible that there is an edge $e$ such that for all $t \in T_r$, we have $e \in E(Tr)$? In other words, is it possible that there is a directed edge of $G$ belongs to all possible spanning trees with $r$ as root?

BTW : My guess is that it is impossible.

Edit : I meant to say "directed graph"

-

Unless I misunderstand something, of course it is possible. There will always be such an edge if the graph can be divided into two parts with only two edges (one in each way) between them.

E.g. the full simple graph on two vertices. There is only one spanning tree starting at each vertex and it has one edge.

-
How about directed graph? – ablmf Jun 24 '12 at 1:10
@ablmf: I did not talk about any undirected graphs. I meant full as a directed graph. Not that it makes any substantial difference in this case, really. – tomasz Jun 24 '12 at 1:12