[Math] Spanning tree of a strongly connected directed graph.

graph theory

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"

Best Answer

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.

Related Question