# Triangle-free labeled graphs

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.

## 2 Answers

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.

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.