3
$\begingroup$

Possible Duplicate:
Spanning Trees of the Complete Graph Avoiding a Given Tree

Two edges $\{a,b\}, \{c,d\}$ are crossing if $a

How many non crossing spanning trees in $K_n$ exist which contain a given edge? The idea of letting two trees grow from the vertices of the fixed edge doesn't guarantee that the resulting tree is non-crossing.

  • 0
    Oh you're right, I couldnt find that, so let me change my question to the more advanced problem.2011-11-18
  • 0
    Do you mean you have a fixed drawing of the complete graph graph on n vertices in the plane? If so, are the edges always straight line segments or do you allow curved edges?2011-11-18
  • 0
    @Joseph Malkevitch No its an abstract graph, see my definition of crossing2011-11-18
  • 0
    The proof in the http://math.stackexchange.com/questions/59100/spanning-trees-of-the-complete-graph-avoiding-a-given-tree question won't work here2011-11-19
  • 0
    @Fred So the edges of the complete graph come with distinct labels which can be compared in size?2011-11-19
  • 0
    No but the vertex set can be regarded as {1,...,n}2011-11-19

0 Answers 0