-1
$\begingroup$

What is the probability that there is an edge in an undirected random graph having m vertices?[assume prob of edge between 2 vertices - 1/2]

how to think in this type of problem.

probability that an edge exists between 2 vertices = 1/2

$(1/2)^{m-1}$ is probability of m length path.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ I am not understanding the question. An edge only ever has two vertices, its two end-points. The graph can have $m$ vertices, sure. Are you asking what the probability is that a random graph with $m$ vertices has at least one edge where each edge independently is included with probability $p=\frac{1}{2}$? What is difficult about that problem? Could you answer the related question, "what is the probability that when flipping $\binom{m}{2}$ fair coins in a row that they all turn out to be tails?" $\endgroup$ – JMoravitz Dec 4 '19 at 14:13
  • 1
    $\begingroup$ If you are asking what the probability is that a random graph contains a path of length $m$, then we've lost a variable here somewhere... how many vertices are in the graph? Also $m$? So you are asking what the probability is that there is a hamiltonian cycle? Or are there $n$ vertices instead which hasn't been mentioned yet until now? Why would you expect this to be easily calculable? $\endgroup$ – JMoravitz Dec 4 '19 at 14:19
  • 1
    $\begingroup$ There must be some sort of language barrier here or translation error. An edge has two vertices. Period. Never any more, never any less (unless you are talking about hypergraphs or loops). If you have "two end vertices" and "six vertices inbetween them" what you are more probably describing is a path, not an edge. A path is made up of many edges. $\endgroup$ – JMoravitz Dec 4 '19 at 14:50
  • 1
    $\begingroup$ Certainly not. It is in fact a very difficult question which I only see a solution that involves heavily tedious casework. See this related question for another discussion on the problem for a partial but still incomplete solution to get an idea on the bounds. $\endgroup$ – JMoravitz Dec 4 '19 at 15:01
  • 1
    $\begingroup$ You mention that "this is a question in competitive exam", could you share a link to the original source? $\endgroup$ – JMoravitz Dec 4 '19 at 15:33
0
$\begingroup$

Am I misreading this? By definition every edge exists between precisely two vertices, except for loops which exist on one. Between fewer than 1 vertices you havent got an edge at all. The point is, every edge has two endpoints. A single edge cannot connect more than two vertices. Thus $m$ can only be 1 or 2. For all other values of $m$ the probability must necessarily be 0 because the scenario is impossible.


Since every complete graph has $\binom{m}{2}$ two-vertex edges, and potentially $m$ one-vertex edges (loops), then in a completely random graph there are $\binom{m}{2} + m $ total edges. These are the only possible undirected edges in a simple graph. If you want generalize then there is an infinitude of possible edges between any two vertices.

So $\binom{m}{2} + m $ is the possible number of edges. Or simply $\binom{m}{2}$, if there are no loops. This is the denominator of any probability fraction you come up with.

$\endgroup$
  • $\begingroup$ sir pls see my above comment and pic in edited part. Pls correct if i am wrong. $\endgroup$ – Nascimento de Cos Dec 4 '19 at 14:50
  • $\begingroup$ The bottom two graphs you ask are different are in fact the same graph. $\endgroup$ – SquishyRhode Dec 4 '19 at 14:51
  • 1
    $\begingroup$ What you are asking is not graph theory at all, but Euclidean geometry. You want to know the probability that $m-2$ points are colinear with some other two points. I assure you such a geometrical figure would be nearly impossible if chosen randomly. $\endgroup$ – SquishyRhode Dec 4 '19 at 14:53
  • $\begingroup$ exactly. Why it is not possible? can u please elaborate (atlease some hints) $\endgroup$ – Nascimento de Cos Dec 4 '19 at 14:54
  • 1
    $\begingroup$ Because its impossible to randomly choose just 3 points that do this, much less $m$. Two points - your endpoints - make a line. It doesnt matter where in space you choose them, they will always make a line. Now randomly choose a third point anywhere in space. Do you think its more or less likely it will be on the line? $\endgroup$ – SquishyRhode Dec 4 '19 at 14:58

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.