Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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"

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.