Probability of segments connecting six points

Question

Question: You can draw edges between any two vertices of an empty graph with $6$ vertices and you have the same chance of drawing each edge. Find the probability that "there exists three vertices that any two of them are connected or any two of them are not connected".

What I tried: index the vertices and there are 15 different segments so there are $2^{15}$cases in total.

Cases for existence of three connected vertices: connect arbitrary three vertices and then decide the 12 edges left. ${6\choose 3} * 2^{12}$.

Cases for existence of three not connected vertices: choose arbitrary three vertices and not connect them and then decide the 12 edges left. ${6\choose 3} * 2^{12}$.

Cases for both: connect arbitrary three vertices and not connect the three left . And there are $3 * 3 = 9$ edges between connected vertices and disconnected vertices. ${6\choose 3} * 2^9$

The problem is that $\frac{{6\choose 3} * 2^{12} + {6\choose 3} * 2^{12} - {6\choose 3} * 2^{9}}{2^{15}} > 1$.

Could you tell me where I went wrong? Thanks in advance.

Answer 1

Actually, despite what I claimed in the comment, your question does not depend on the random graph model you are using. By Ramsey’s Theorem any graph with 6 vertices contains either a full 3-vertice subgraph or an empty 3-vertice subgraph, so your probability is 1 in any case. You can find more information about Ramsey’s theorem and Ramsey Numbers under this link: https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem

Answer 2

A quick look suggests you forgot the case where one of the points is a member of both the connected and disconnected groups.

Edit: in fact, you are double counting a ton of the graphs, for example the completely connected graph gets counted 20 times. My suggestion on how to approach this problem would be to instead consider the graphs where neither the 3-clique of connected vertices nor the 3-clique of disconnected vertices exist. Do such graphs really exist?

Answer 3

This is Ramsey's Theorem. Here the "colors" are either "in the graph" or "not in the graph". So just color every edge red or blue at random. The odds of getting a monochromatic triangle are 1.

Suppose the edges of a complete graph on 6 vertices are coloured red and blue. Pick a vertex, v. There are 5 edges incident to v and so (by the pigeonhole principle) at least 3 of them must be the same colour. Without loss of generality we can assume at least 3 of these edges, connecting the vertex, v, to vertices, r, s and t, are blue. (If not, exchange red and blue in what follows.) If any of the edges, (r, s), (r, t), (s, t), are also blue then we have an entirely blue triangle. If not, then those three edges are all red and we have an entirely red triangle. Since this argument works for any colouring, any K6 contains a monochromatic K3, and therefore R(3, 3) ≤ 6.

Wiki