How many trees are there on vertex set $[n]$ that contain a given edge $uv$? [duplicate]
up vote
1
down vote
favorite
This question already has an answer here:
How many different spanning trees of $K_n setminus e$ are there?
3 answers
How many trees are there on vertex set $[n]$ that contain a given edge $uv$?
If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are total $(n-1)^{(n-3)}$ trees with vertex set $[n-1]$ and a given edge $uv$.
Is this correct?
combinatorics graph-theory trees
edited Nov 26 at 16:38
Shaun
8,190113577
asked Nov 26 at 16:30
thetraveller
1515
marked as duplicate by Trevor Gunn, Community♦ Nov 26 at 17:05
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
up vote
1
down vote
favorite
This question already has an answer here:
How many different spanning trees of $K_n setminus e$ are there?
3 answers
How many trees are there on vertex set $[n]$ that contain a given edge $uv$?
If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are total $(n-1)^{(n-3)}$ trees with vertex set $[n-1]$ and a given edge $uv$.
Is this correct?
combinatorics graph-theory trees
edited Nov 26 at 16:38
Shaun
8,190113577
asked Nov 26 at 16:30
thetraveller
1515
marked as duplicate by Trevor Gunn, Community♦ Nov 26 at 17:05
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
– Trevor Gunn
Nov 26 at 16:54
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This question already has an answer here:
How many different spanning trees of $K_n setminus e$ are there?
3 answers
How many trees are there on vertex set $[n]$ that contain a given edge $uv$?
If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are total $(n-1)^{(n-3)}$ trees with vertex set $[n-1]$ and a given edge $uv$.
Is this correct?
combinatorics graph-theory trees
edited Nov 26 at 16:38
Shaun
8,190113577
asked Nov 26 at 16:30
thetraveller
1515
This question already has an answer here:
How many different spanning trees of $K_n setminus e$ are there?
3 answers
How many trees are there on vertex set $[n]$ that contain a given edge $uv$?
If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are total $(n-1)^{(n-3)}$ trees with vertex set $[n-1]$ and a given edge $uv$.
Is this correct?
This question already has an answer here:
How many different spanning trees of $K_n setminus e$ are there?
3 answers
combinatorics graph-theory trees
combinatorics graph-theory trees
edited Nov 26 at 16:38
Shaun
8,190113577
asked Nov 26 at 16:30
thetraveller
1515
edited Nov 26 at 16:38
Shaun
8,190113577
asked Nov 26 at 16:30
thetraveller
1515
edited Nov 26 at 16:38
Shaun
8,190113577
edited Nov 26 at 16:38
Shaun
8,190113577
edited Nov 26 at 16:38
Shaun
8,190113577
8,190113577
asked Nov 26 at 16:30
thetraveller
1515
asked Nov 26 at 16:30
thetraveller
1515
asked Nov 26 at 16:30
thetraveller
1515
1515
marked as duplicate by Trevor Gunn, Community♦ Nov 26 at 17:05
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Trevor Gunn, Community♦ Nov 26 at 17:05
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
– Trevor Gunn
Nov 26 at 16:54
add a comment |
Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
– Trevor Gunn
Nov 26 at 16:54
Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
– Trevor Gunn
Nov 26 at 16:54
Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
– Trevor Gunn
Nov 26 at 16:54
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
$n^{n-2}cdot(n-1)$ such trees.
By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
$$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
trees where $uv$ happens to be the distinguished edge.
answered Nov 26 at 16:37
Hagen von Eitzen
275k21268495
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
$n^{n-2}cdot(n-1)$ such trees.
By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
$$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
trees where $uv$ happens to be the distinguished edge.
answered Nov 26 at 16:37
Hagen von Eitzen
275k21268495
add a comment |
up vote
1
down vote
accepted
A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
$n^{n-2}cdot(n-1)$ such trees.
By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
$$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
trees where $uv$ happens to be the distinguished edge.
answered Nov 26 at 16:37
Hagen von Eitzen
275k21268495
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
$n^{n-2}cdot(n-1)$ such trees.
By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
$$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
trees where $uv$ happens to be the distinguished edge.
answered Nov 26 at 16:37
Hagen von Eitzen
275k21268495
A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
$n^{n-2}cdot(n-1)$ such trees.
By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
$$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
trees where $uv$ happens to be the distinguished edge.
answered Nov 26 at 16:37
Hagen von Eitzen
275k21268495
answered Nov 26 at 16:37
Hagen von Eitzen
275k21268495
answered Nov 26 at 16:37
Hagen von Eitzen
275k21268495
answered Nov 26 at 16:37
Hagen von Eitzen
275k21268495
275k21268495
add a comment |
add a comment |
Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
– Trevor Gunn
Nov 26 at 16:54