I had a programming exam and encountered a probability question which can’t solve even mathematically.
The question was: if in a graph with V vertices and E edges, we choose E edges (suppose edges are hidden or in other words don’t know stretched between which vertices) then evaluate the probability of chosen at least one correct edge?
I can’t understand the problem correctly (we have E edges and chose E edges!) but here is some example which was given and what I tried
Vertex: 3, chosen edge: 1 --> .3333
Vertex: 3, chosen edge: 2 --> 1.0000
Vertex: 9, chosen edge 6 --> .6951
The formula which I think might give the correct answer:
(total- 0 correct edge)/total
But that doesn’t work, for instance in third example above
(C(9,6)-C(6,0)C(6,6))/C(9,6)=.9880
Also about second example above I don’t know how that possible to be 1 cause may we chose both edges wrong.
It looks like you pick an $E$ edge graph on the given $V$ vertices and check if that graph has at least one edge in common with the given $E$ edge graph. There are ${V\choose 2}\choose E$ graphs to pick from, and the praphs have no edge in common if the $E$ edges are actually picked from the ${V\choose 2}-E$ non-edges. Hence the answer is $$1-\frac{{V\choose 2}-E\choose E}{{{V\choose 2}\choose E}} $$