We consider a configuration graph with N vertices, whose degrees are independent and identically distributed according to power-law distribution with the parameter τ = τ(N). They are equal to the number of each vertex’s numbered semi-edges. The graph is constructed by joining all of the semi-edges pairwise equiprobably to form edges. Such models can be used to adequately describe various communication networks and Internet topologies. The properties of the graph depend on the behaviour of the parameter τ. The paper investigates the conditions under which a random configuration graph is asymptotically connected as N → ∞.