Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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}$. – Gyu Eun Lee Jan 21 '13 at 3:11
The number of graphs with $n$ vertices and $k$ edges should be: $n(n-1)/2 \choose k$ – M.M Jul 13 '15 at 9:33
@M.M That's the easy part. Now constrain the triangle count :-) – Szabolcs Jul 13 '15 at 10:34

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.