*Europhys. Lett.*,

**75**(1), pp. 8-14 (2006)

DOI: 10.1209/epl/i2006-10070-4

## Sudden emergence of *q*-regular subgraphs in random graphs

**M. Pretti**

^{1}and M. Weigt^{2}^{1}INFM-CNR, Dipartimento di Fisica, Politecnico di Torino Corso Duca degli Abruzzi 24, I-10129 Torino, Italy

^{2}Institute for Scientific Interchange - Viale Settimio Severo 65, I-10133 Torino, Italy

received 31 March 2006; accepted 5 May 2006

published online 31 May 2006

** Abstract **

We investigate the computationally hard problem whether a random graph
of finite average vertex degree has an extensively large *q*-regular
subgraph, *i.e.*, a subgraph with all vertices having degree equal
to *q*. We reformulate this problem as a constraint-satisfaction
problem, and solve it using the cavity method of statistical physics
at zero temperature. For *q*=3, we find that the first large
*q*-regular subgraphs appear discontinuously at an average vertex
degree
and contain immediately about
of all vertices in the graph. This transition is extremely close to
(but different from) the well-known 3-core percolation point
. For *q*>3, the *q*-regular subgraph
percolation threshold is found to coincide with that of the *q*-core.

**PACS**

05.20.-y - Classical statistical mechanics.

02.50.-r - Probability theory, stochastic processes, and statistics.

89.20.-a - Interdisciplinary applications of physics.

**©**

*EDP Sciences 2006*