3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ How many segments are you to draw? $\endgroup$ – L. Scott Johnson Feb 7 at 13:30
  • $\begingroup$ Hi! Welcome to MSE! It seems that your question is about random graphs. Could you explain, please, what random graph model are you using? Without knowing that, we will not be able to answer your question... $\endgroup$ – Yanior Weg Feb 7 at 13:50
  • $\begingroup$ @L.ScottJohnson 0 to 15. $\endgroup$ – Adwin1033 Feb 7 at 14:01
  • $\begingroup$ @YaniorWeg I have not learned any graph theory yet . What information is missing? $\endgroup$ – Adwin1033 Feb 7 at 14:06
  • $\begingroup$ @Adwin1033, there are different ways of drawing random edges. And the probability of an outcome usualy depends on which of them you are using. You can find several most commonly used random graph models under this link: en.m.wikipedia.org/wiki/Random_graph And if you want more information, there is a book on random graphs, written by A.M. Raigorodskiy $\endgroup$ – Yanior Weg Feb 7 at 14:11
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Oh, I did count repeatedly. Such graph does not exist. I wanted to prove it by showing probability of its opposite is 1. $\endgroup$ – Adwin1033 Feb 7 at 13:59
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.