Counting Two-graphs Related to Trees

Abstract

In an earlier paper, I showed that the classes of pentagon-free two-graphs and of pentagon-and-hexagon-free two-graphs could be represented in terms of trees. This paper gives formulae for the numbers of labelled objects in each of these classes, as well as the numbers of labelled reduced two-graphs in each class. The proofs use various enumeration results for trees. At least some of these results are well-known. To make the paper self-contained, I have included proofs.