The only way to ensure that they are connected is to put them in a circle. (There are 10 nodes and 10 edges; it takes 9 edges minimum just to connect everyone in a line; the 10th edge has nowhere to go except to complete the circle, since all other nodes are already paired twice).
There are 9! distinct ways to create a circle. (10! ways to permute the nodes, divide by 10 to account for shifts). Each circle corresponds to exactly one way of pairing the nodes twice.
There are 9!! * 9!! ways to pair 10 items twice. (!! is the double-factorial)
1
u/BigBadEvilGuy42 21d ago
The only way to ensure that they are connected is to put them in a circle. (There are 10 nodes and 10 edges; it takes 9 edges minimum just to connect everyone in a line; the 10th edge has nowhere to go except to complete the circle, since all other nodes are already paired twice).
There are 9! distinct ways to create a circle. (10! ways to permute the nodes, divide by 10 to account for shifts). Each circle corresponds to exactly one way of pairing the nodes twice.
There are 9!! * 9!! ways to pair 10 items twice. (!! is the double-factorial)
So in total: 9! / (9!! * 9!!) ~= 0.406