Probabilistic Characteristics of Graphs with Large Connectivity

It is possible to associate with every finite graph $G$ a function $f_G(p)$, $0\leqslant p\leqslant1$, representing the probability that $G$ will cease to be connected under the condition that every edge is severed with probability $p$. It is shown that for graphs $G$ with large connectivity the function $f_G(p)$ “almost” coincides with the characteristic function of a certain interval (the precise formulation is given in Sec. 1.1). This proposition is proved by means of Theorems 2.2 and 2.4 on subsets in Hamming space.