Stay connected

Probability Level 3

You have four nodes and any two have a 50% chance of having a direct connection between them.

Is the resulting graph more likely to be connected or not?

Connected Not connected Either is equally likely

Geoff Pilling by Geoff Pilling , 53, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Jeremy Galvagni
Nov 25, 2018

Of the 6 possible connections: if 0,1,2 are chosen the graph is not connected. If 4,5,6 are chosen the graph will be connected.

So far things look perfectly balanced. We just need to consider what happens when 3 connections are chosen.

Of the C(6,3)=20 ways of choosing 3, only 4 do not connect the graph. (The four triangles.)

So overall, the graph is a bit more likely to be connected.

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Geoff Pilling
Nov 24, 2018

Of the 2 6 = 64 2^6 = 64 ways the four nodes could be connected, 38 result in a connected graph.

38 64 > 0.5 \frac{38}{64} > 0.5

Therefore, they are more likely to be connected.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

I think with the current wording it is possible to misinterpret complete graph as the graph with all six edges. Maybe you could say something like the resulting graph

Henry U - 2 years, 6 months ago

Log in to reply

Ok, I've clarified the question a bit...

Geoff Pilling - 2 years, 6 months ago

Oh drat. My interpretation was that two nodes are connected if there is some path between them and not that they are necessarily directly connected, (i.e., no intermediary node required to bridge the connection), which appears to be the interpretation your solution is based on. From my interpretation I concluded the graph was less likely to be connected.

Brian Charlesworth - 2 years, 6 months ago

Log in to reply

Hmmm... Ok I've rephrased the question... Hopefully it's a little clearer now...

Geoff Pilling - 2 years, 6 months ago
Abhishek Sinha
Dec 9, 2018

First, notice that a graph and its complement has the same probability mass. Now consider any disconnected configuration. This could be of the following two types (1) A single node is disconnected from the rest, and (2) Two nodes are disconnected from the rest of the two nodes. In both of these configurations, the complement graph is a connected graph. Hence, for any disconnected instance, there is a unique connected instance of the same probability. Therefore, it follows that the random graph is more likely to be connected .

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...