Wikipedia:Reference desk/Archives/Mathematics/2023 August 24

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 24

Graph Theory question (from Fantasy & Gates)

The discussion boiled down to the following mathematics problem. Of all of the possible graphs with 10 nodes and 3 undirected edges at each node (and no loops), what percentage of them have two completely unconnected pieces? For example the following is two completely different pieces, (a tetrahedron and a hexagon with a connection to the opposite corner)

• A: BCD
• B: ACD
• C: ABD
• D: ABC
• E: FHJ
• F: EGI
• G: FHJ
• H: EGI
• I: FHJ
• J: EGI

OTOH a pentagonal prism

• A: BEF
• B: ACG
• C: BDH
• D: CEI
• E: ADJ
• F: AGJ
• G: BFH
• H: CGI
• I: DHJ
• J: EFI

is a single set of pieces. (as would be a triangle connected to a heptagon with two cross bars and a square connected to a hexagon with one crossbar, but have *no* idea if a particular setup is the same as another ) I'm guessing the percentage with completely different pieces is fairly low, but no idea how to calculate it.Naraht (talk) 01:13, 24 August 2023 (UTC)

It helps to know some of the jargon to search on; you're talking about trivalent (or cubic) graphs, and what percentage are connected. The answer depends on whether you're talking about labelled or unlabelled graphs. If makes a difference because if one graph has more symmetry than another then it has fewer labelled versions than the other graph. For the unlabelled case you can find the answer by comparing oeis sequences OEIS: A002851 and OEIS: A005638. Assuming I counted correctly there are 19 connected out of 21 total, making 2 graphs that are not connected. For labelled graphs (OEIS: A004109 and OEIS: A002829) the numbers are 11166120 connected of 11180820 total. For unlabelled graphs the percentage is a lot lower, about .2% compared to 20% for unlabeled graphs. I'm not really sure how you'd actually calculate it, but oeis gives some links. --RDBury (talk) 03:01, 24 August 2023 (UTC)

Should be worth noting that the 2 graphs that you mentioned are not connected are indeed a tetrahedron and a component with 6 vertices, of which you can construct 2 different ones as per the OEIS sequence (see table of simple cubic graphs.) In general, the number of unconnected unlabeled cubic graphs on $2n$ vertices (OEIS: A165653) is precisely the sum over all distinct partitions (here we use only even partitions, since naturally the number of cubic graphs on odd vertices is 0) of $2n$ of the product of the number of connected unlabeled cubic graphs over the numbers in the partition. That's a real handful, so I'll try to summarize it as:

$\sum _{\underset {0<n_{1}\leq \ldots \leq n_{k}}{n_{1}+\ldots +n_{k}=n}}\prod _{i=1}^{k}A002851(n_{i})$

This is naturally a general formula that also extends to finding unconnected unlabeled [insert property here] graphs in general, assuming you know the the number of connected unlabeled [property] graphs up to that point. And of course, if one wants exactly two components, then this is readily modified to:

$\sum _{m=1}^{n-1}A002851(m)A002851(n-m)$

Of course, this isn't particularly illuminating as a formula, and it doesn't readily yield to a nice closed-form expression, but at least it gives some way to calculate the number of nonconnected unlabeled cubic graphs on two components. GalacticShoe (talk) 14:24, 24 August 2023 (UTC)

The generalization to more gates is interesting, I'm specifically wondering about labelled (the 10 vertices are 10 specific kingdoms). And having the 10 kingdoms connected 11166120 times out of every 11180820 times that the gates shift would make the .2% of the time (1 in 500ish) when the entire empire is not connected an event that a story could be based on. I had missed on the other way to do the 6 vertices alone. The extension that I am wondering about is if each vertex had 3 outgoing directed edges and 3 incoming directed edges, how rare would it be to not have every node reachable from every other node. That would have to be *incredibly* small.Naraht (talk) 14:58, 24 August 2023 (UTC)