# undirected random graph: common neighbors between two vertices

I have a undirected random graph with node degree distribution $P(k)$, I pick a random vertex $v_0$ and I randomly select a neighbor $v_1$ (the selection is made with uniform probability).

What is the probability that v1 has at least $1$ neighbor which is not a neighbor of $v_0$?

Another formulation of the question: if the expected node degree of v1 is $<k>_1$, what is the probability that v0 and v1 share $<k>_1 - 1$ neighbors?

Thanks

Michele

-
Your formulation seems a bit off. When you say node degree distribution $P(k)$, do you mean the degree distribution of a randomly chosen vertex? Or are you fixing a deterministic sequence of degrees? The issue is once you observe a node degree, all other nodes become conditioned on what you observe, so this question seems difficult. –  Alex R. Sep 15 '12 at 16:19