PropositionStatement: AI-generatedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Single-vertex degree laws and the shared-edge dependence

Statement

Let $n \geq 1$ and $p \in [0, 1]$ , and let $G (n, p)$ be the simple graph on $[n]$ whose possible edges occur independently with probability $p$ . Write $A_{u v} = A_{v u}$ for the indicator that the edge ${u, v}$ occurs, and define the degree $d (u) = \sum_{w \in [n] ∖ {u}} A_{u w}$ . Then $d (u)$ has law $Bin (n - 1, p)$ for every vertex $u$ .

For distinct vertices $u, v$ , put $R_{u} = \sum_{w \notin {u, v}} A_{u w}$ and $R_{v} = \sum_{w \notin {u, v}} A_{v w}$ . The variables $A_{u v}, R_{u}, R_{v}$ are mutually independent, while $d (u) = A_{u v} + R_{u}$ and $d (v) = A_{u v} + R_{v}$ share the same edge indicator. Consequently $Cov (d (u), d (v)) = p (1 - p)$ . Identically distributed degrees need not be independent; a count of vertices of a given degree is not in general binomial.

Statement references

The Erdős-Rényi finite random graph G(n,p)

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials

Pairwise and mutual independence of finite-valued random variables

Variance, standard deviation, and covariance on a finite probability space

Facts & Assumptions

Given: $n \geq 1$ , $p \in [0, 1]$ , and the graph and edge indicators in the Statement.

Goal: Establish the degree law, the independence of the three displayed terms, their covariance, and the qualification about degree counts.

[F1]

The graph has one mutually independent Bernoulli $(p)$ indicator for each unordered pair of distinct vertices; a simple graph has no loops. (The Erdős-Rényi finite random graph G(n,p), A finite simple graph is a finite vertex set together with a set of two-element vertex subsets)

[F2]

A sum of $k$ mutually independent Bernoulli $(p)$ variables has the binomial $(k, p)$ law, including the empty sum when $k = 0$ . (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials)

[F3]

Mutual independence means that joint probabilities of specified values factor over any subfamily. (Pairwise and mutual independence of finite-valued random variables)

[F4]

Covariance is the expectation of the product of centered variables and is bilinear on finite linear combinations; independent square-integrable variables have zero covariance. (Variance, standard deviation, and covariance on a finite probability space, Variance and covariance identities for random variables, Independence forces covariance to vanish)

[F5]

A Bernoulli $(p)$ variable has variance $p (1 - p)$ . (A Bernoulli(p) variable has mean p and variance p(1-p); a binomial(n,p) variable has mean np and variance np(1-p))

Proof

technique · direct

1.1F1F2

For a fixed $u$ , its possible incident edges are precisely the $n - 1$ distinct pairs ${u, w}$ with $w \neq u$ . Their indicators are mutually independent Bernoulli $(p)$ variables, so their sum $d (u)$ is binomial $(n - 1, p)$ , also when $n = 1$ .

1.2F1F3algebra

For distinct $u, v$ , the edge-index sets used by $A_{u v}$ , $R_{u}$ and $R_{v}$ are pairwise disjoint. For prescribed values of the three variables, sum the joint probabilities over the edge-indicator configurations giving those values. The factorization in [F3] makes each configuration probability a product over the three disjoint blocks; the finite sum consequently factors into the three marginal probabilities. Thus the three variables are mutually independent. This includes $n = 2$ , when both residual sums are constant zero. The displayed degree decompositions follow by separating the edge ${u, v}$ from each incident-edge sum.

2.1step 1.2F4F5

All variables are bounded. Bilinearity and the zero covariance of independent variables give $Cov (d (u), d (v)) = Cov (A_{u v}, A_{u v}) = Var (A_{u v}) = p (1 - p)$ . For $0 < p < 1$ this is nonzero, so the two degrees are not independent.

3.1step 1.1F1F2algebra∎

For $n = 2$ and $0 < p < 1$ , the number of vertices of degree one is $2 A_{12}$ : it is zero with probability $1 - p$ and two with probability $p$ . A binomial law with two trials and success probability $p$ assigns probability $2 p (1 - p) > 0$ to one, and no other binomial law can have exactly this nondegenerate support ${0, 2}$ . Hence even though the degrees have the same marginal law, their degree count need not be binomial.

Depends on

Used by · 11

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.