Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many labelled undirected graphs are there with precisely $n$ vertices, $k$ edges, and $t$ triangle subgraphs? (By triangle I mean a graph with three vertices and three edges.)

(Clarification: I am interested only in graphs with no self loops or multiple edges. The graphs do not need to be connected.)

I would appreciate any pointers to results on this problem (exact or approximate). The results I am able to find are typically for unlabelled graphs (e.g. a count up to $n=12$), but in this case I am interested in labelled ones.

I am also interested in possible computational methods for this that are better than brute enumeration.

share|improve this question
I haven't the faintest myself, but in the hope that this leads you somewhere: Cayley's formula for the numbers of labeled trees on $n$ vertices in $n^{n-2}$. –  neuguy Jan 21 '13 at 3:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.