0
$\begingroup$

Find all the non- isomorphic forests with five vertices and two or more components.

-I understand the concept of this question and have drawn out several graphs fitting these constraints, although I know there must be an equation that I can plug vertices and component values into to get the answer. The only formula I know from this chapter in my book that was remotely similar was Cayley's theorem which proved to be no help. Any help is appreciated.

$\endgroup$
  • 1
    $\begingroup$ The numbers are small enough that I’d do this one by brute force. There is one forest with $5$ components and one with $4$. There are three with $3$ components, and it’s not hard to find the ones with $2$ components, either. $\endgroup$ – Brian M. Scott Oct 17 '15 at 19:10
  • $\begingroup$ I understand i was just worried about missing a possibility, how do you know that these are all the possible graphs? Is there a way to check? Also, for the case with 4 components it looks as if you are not counting the vertices as unique, meaning the one connection between two vertices (say 1 and 2) is the same as all independent except a connection between say 3 and 4. Is that the correct way to approach all cases.? $\endgroup$ – D.Peterson Oct 17 '15 at 19:19
  • $\begingroup$ Mostly just by being careful. For instance, there are two trees on $3$ vertices and only one on $2$ vertices, so there must be two forests that have a tree with $3$ and another tree with $2$ vertices. The same kind of analysis on a $4$-$1$ split just requires making sure that I find all of the $4$-vertex trees. $\endgroup$ – Brian M. Scott Oct 17 '15 at 19:21
  • $\begingroup$ I edited my comment above yours with additional questions. $\endgroup$ – D.Peterson Oct 17 '15 at 19:25
  • $\begingroup$ As I read the problem statement, the vertices are unlabelled, so a forest with $4$ components is simply three isolated vertices and a $K_2$. $\endgroup$ – Brian M. Scott Oct 17 '15 at 19:27

Your Answer

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

Browse other questions tagged or ask your own question.