4
$\begingroup$

The number of connected labeled graphs with $n$ edges and $n$ nodes are listed in OEIS A057500.

I suspect the following must be known but I can't find a reference to it.

Question. How many among the above graphs are triangle-free?

NOTE. This problem is connected to my other MO question here.

$\endgroup$
9
$\begingroup$

Since a connected graph with $n$ vertices and $n$ edges is unicyclic, you just need to subtract the ones whose cycle is a triangle (http://oeis.org/A053507) from the total (http://oeis.org/A057500).

Starting at $n=4$, I get 3, 72, 1500, 32280, 748440, 18898992, 520107840, 15555704400, 503580654720, 17569154733240, ... which is not in OEIS by itself.

$\endgroup$
4
$\begingroup$

The following formula is useful for counting such things: $\sum \prod z_i^{d_i-1}=(\sum z_i)^{k-2}$, where the summation is taken over all trees on $k$ labelled vertices, and $d_i$ denotes the degree of vertex $i$. We count the number of connected labelled graphs on $n$ vertices with unique cycle which is a triangle. We choose this triangle by $\binom{n}3$ ways, and contract it. We get a tree on $k=n-2$ vertices and have to sum up $3^{d_1}$ over such trees, where $d_1$ is a degree of the contracted vertex. From above, it equals $3n^{n-4}$ (take $z_1=3,z_i=1$ for $i>1$.) So, the total number of graphs we count equals $3\binom{n}3n^{n-4}=\binom{n-1}2n^{n-3}$, as the reference http://oeis.org/A053507 from Brendan McKay's answer claims.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.