1
$\begingroup$

I'd like to know if Inclusion/Exclusion could be useful to count all the possible graphs that can be drawn with n vertices and no vertex having 2 or more lines attached, and how to apply it.

Would it be too naive to expect a nice-looking formula out of this?. Maybe... we need Polya counting?, maybe another theorem to solve it?, something involving complements to simplify the question?. I'd appreciate to see your thoughts on this, guys.

EDIT: I'm considering graphs with general types of symmetries (not just $S_n$).

$\endgroup$
4
  • $\begingroup$ These graphs are exactly disjoint unions of either paths or cycles, so the count is not too hard, depending on whether you want the unlabeled or labeled count. $\endgroup$ – Qiaochu Yuan Oct 2 '20 at 20:20
  • $\begingroup$ Qiaochu. Some vertices are interchangeable (unlabelled) and others not (they're labelled), that's why I mentioned Polya counting because it allows me to specify the group of symmetries. This is my first approach to graphs, actually, and it's mainly becaise of a hobby, so... yeah, I'd appreciate if you could ellaborate on your previous comment abot more, please (?). $\endgroup$ – JuanC97 Oct 2 '20 at 20:25
  • 1
    $\begingroup$ Oh, sorry, I misread your question; I thought you were asking for degree $\le 2$, not degree $<2$. The degree $\le 2$ case is much more interesting! $\endgroup$ – Qiaochu Yuan Oct 2 '20 at 20:52
  • 1
    $\begingroup$ There are more graphs but it's still possible to classify them. I posted this as a separate question here, which I'll answer in a day or so: math.stackexchange.com/questions/3849265/… $\endgroup$ – Qiaochu Yuan Oct 2 '20 at 21:11
2
$\begingroup$

If no vertex has $2$ or more lines attached, then every vertex has at most one line. Then every vertex is either isolated, having no edges, or it is in a pair. If the vertices are unlabeled then this comes down to writing $n$ as a sum of $1$'s and $2$'s, so there are $\lfloor\tfrac n2\rfloor+1$ such graphs on $n$ vertices.

$\endgroup$
2
  • 1
    $\begingroup$ And the number of labeled such graphs is given by the involution numbers: en.wikipedia.org/wiki/Telephone_number_(mathematics) $\endgroup$ – Qiaochu Yuan Oct 2 '20 at 21:01
  • $\begingroup$ These two answers account for the $S_n$ and $S_1^n$ cases but what about general symmetries?. Polya counting allows one to count graphs on $n$ vertices with $k$ lines and arbitray symmetries, isn't it there something useful to count k-edge matchings?, not even Inclusion/exclusion works? $\endgroup$ – JuanC97 Oct 2 '20 at 23:02

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.