Summary: This paper consists of two related parts. In the first part the theory of $D$-finite power series in several variables and the theory of symmetric functions are used to prove $P$-recursiveness for regular graphs and digraphs and related objects, that is, that their counting sequences satisfy linear homogeneous recurrences with polynomial coefficients. Previously this has been accomplished only for small degrees, for example, by Goulden, Jackson and Reilly, then by Goulden and Jackson, finally by Read. These authors found the recurrences satisfied by the sequences in question. Although the methods used here are in principle constructive, we are concerned here only with the question of existence of these recurrences and we do not find them.