# Specific subset of verticies are degree 1 in random graph probability

On a random graph $$G_{n,p}$$, I want to know the probability that some subset of verticies is degree one. Take it to be the verticies $$A = \{1,2,\dots,k\}$$.

My approach for this is to notice that if they are all degree one, then there must be an even number of verticies in $$A$$ that all pair with one another, and the rest of the verticies that don't pair within another vertex in $$A$$ must connect to exactly one vertex in $$[n] - A$$.

I them sum over the probability of even numbers $$2j\leq k$$ such that the $$2j$$ verticies all pair with one another and nothing else, and the $$k-2j$$ verticies all connect to exactly one vertex in $$[n]-A$$ and nothing else.

I want to know if I'm missing anything, or if this is a valid approach.

• What does that mean: subset of verticies is degree one. – Maria Mazur Apr 6 at 16:07
• @MariaMazur Presumably, that all the vertices in that subset are degree one, but don't nitpick. – Misha Lavrov Apr 6 at 16:13

This is valid, especially if you're trying to compute the exact probability. (You should also, if you're not doing so already, include a factor for the number of ways to choose $$j$$ edges between $$k$$ vertices.)

If the random graph is sparse (which it ought to be: for $$p \gg \frac{\log n}{n}$$, we don't get any degree-one vertices with high probability) and $$A$$ is not too large, then looking at edges inside $$A$$ is more work than you need to do, when all you want is an asymptotic probability.

The probability that there are any edges inside $$A$$ is at most $$\binom{|A|}{2}p$$. When this is a $$o(1)$$ term, we can ignore it, and assume $$A$$ is independent. This makes the rest of the calculation much simpler, because you can just multiply the probabilities together for each vertex in $$A$$.

If you are later planning to sum over all choices of $$A$$, you do have to say a bit more than "this is a $$o(1)$$ term" because there are $$O(n^{|A|})$$ such choices. However, even then, the case where $$A$$ is independent dominates all other cases: when $$A$$ is independent, you get to choose $$O(n^{|A|})$$ neighbors for the degree $$1$$ vertices of $$A$$, and when $$A$$ contains $$j>0$$ edges, you only get to choose $$O(n^{|A|-2j})$$ neighbors.