- #1

joypav

- 151

- 0

**Problem:**

Suppose that the function $p : N \rightarrow [0, 1]$ satisfies $p >> n^{-1}ln(n)$ (i.e. $n^{-1}ln(n) = o(p)$).

**(a)**Prove that as $n \rightarrow \infty$, the random graph $G(n, p)$ has minimum degree at least $\frac{np}{2}$ almost surely.

**Idea:**Look at the degree of each individual vertex $v \in V(G)$. Try to find a bound on the probability of this fixed vertex having a small degree (using Chernoff's Inequality?).

I am not getting to where I think I should with this idea.

Let $X_{u,v}$ be $1$ is $uv \in E(G)$ and $0$ if $uv \notin E(G)$.

Then, $X_v = \sum_{u \in V(G), u \neq v} X_{u,v}$ will give us the degree of $v$.

Also, the $X_{u,v}$'s are uniform/independent (as $G$ is a random graph and edges are picked independently with probability $p$).

Now we may use Chernoff's? How do I use the first thing we assumed... that $p >> n^-1ln(n)$?

**Conclude that for any fixed positive integer k, the random graph $G(n, p)$ has minimum**

(b)

(b)

degree at least k almost surely as $n \rightarrow \infty$.

Last edited: