My thoughts about counting/estimating invalid combinations were really, really wrong, so I won't share them. (I didn't do it on purpose, but it does serve to reinforce something that I tell folks from time to time: Don't take anybody's word for things. Do your own research.)

Let's look again:

Number of nodes = 10.
Total number of possible links = (9 * 10) / 2 = 45.
(So far, so good.)

Now, with 45 links, everything is connected to everything. So, there is exactly one combination to consider, and it is valid. That is, the graph is connected.

Consider 44 links. (That means consider all combinations of where one link has been removed.) There are obviously 45 such combinations. (So far, so good.)

However, there is no way that we can remove one link from and leave 44 still connected in such a way that any node(s) is(are) isolated. I reached this conclusion "by inspection". I didn't prove it mathematically, but I think I could, if pressed, and without resorting to any specific graph theory magic. So my previous report (about the number of valid combinations) was wrong even in this simple case.

Continuing: how about 43 links for the 10 nodes? Since each combination that we are considering has two links removed from the original 45, the total number of combinations is equal to the (number of 45 things, taken 2 at a time) The effect on the graph is the same as before: no way can there be a disconnected graph.

Well, still operating by the seat of our pants: what is the minimum number of links that we can remove that will leave a single node isolated?

Each node starts with 9 links to (all of the) other nodes. If we remove 8 links from a single node, it is still connected to one other node. And, since all of the other nodes will still be connected to each other, then our node is not isolated. So the graph is still connected.

It seems to me that we have to remove nine links to isolate a node.

Is there any way to remove fewer than nine links from various nodes so that the result is a disconnected graph? I think not, and then we can see that for 10 nodes and 36 or more links all combinations will be valid. Right?

In general, supose that the number of nodes is n, then the maximum total number of links is (n-1)*n / 2. That makes every node be connected to every other node. Now if we remove fewer than (n-1) links, there is no way that we can have a disconnected graph. (I think.)

If we remove exactly (n-1) links, there will be n invalid combinations (The n cases where all (n-1) are removed from a single node, leaving that node isolated.)

If we remove more than (n-1) links, then there are more invalid combinations. (Is there a formula for the number of invalid combinations, given n and the number of links? Left as an exercise.)


Bottom line: if the number of nodes is n, then there are no discontinous graphs as long as the number of nodes is greater than ((n-1)*n/2) - (n-1) = (n-1)*(n-2)/2

Therefore with 10 nodes and 39 links, all 8,145,060 combinations are valid.

Did I get it right this time?

Regards,

Dave