Случайные графы.

[Tosha]

Если в графе $G=(V,E)$ с $n$ вершинами минимальная степень вершины равна $\delta$, то

1) Для любого $p\in (0;1)$ существует такое множество вершин $A\subset V$, что в объединении $A$ и множества вершин, не соединенных с ни с какой вершиной из $A$

имеется не более $np+n(1-p)^{\delta+1}$ вершин.

2) Существует такое множество вершин $D \subset V$ , что любая вершина из $V \D$ соединена ребром с некоторой вершиной из $D$, при этом

$|D|\le n\cdot \dfrac{1+\ln(\delta +1)}{\delta+1}$

Рассмотрим первый пункт.

Я так понимаю, что любое возможное ребро из множества $A\subset V$ появляется независимо с вероятностью $0 < p < 1$.
То есть $p=p(v\in A)$ для каждой вершины $v\in A$

Вероятность того, что из $m$ ребер графа ровно $m$ окажутся в множестве $A$ равна $p^m(1-p)^{n-m}$

Пока что только такие идеи есть, больше не знаю за что зацепиться и как использовать минимальную степень вершины графа $\delta$

[Tosha]

Поправка опечатки*

Вероятность того, что из $n$ ребер графа ровно $m$ окажутся в множестве $A$ равна $p^m(1-p)^{n-m}$

-- 10.11.2015, 15:54 --

Или же должно быть $C_n^mp^m(1-p)^{n-m}$?

[Tosha]

Видимо я что-то совсем глупое написал или слишком узкая область на стыке теории графов и теории вероятностей?