Find the number of graphs


#1

Given n ≥ 4, find the number of graphs G = (V, E) with set of vertices V = {1, 2, . . .} having the following structure: a cycle (whose length is not prescribed), with a nonempty chain (the “tail”) attached to the
cycle at one endpoint.


#2

Given n>=4, then the process of assembling this graph with required properties are as follows
a)
first we fix the length l of the cycle then, l>=3 and l>=n-1, because at least one vertex must belong to the tail.
b)
we choose the l vertices which form the cycles which can be done in (n`)ways.
l
c)
we decide in what order the l chosen vertices appear in the cycle as we know that the no of choices is given by l!/(2l).
d)
after that the cycle of length l has been fixed and the remaining (n-l) vertices will form the tail .then we have to decide to what vertices of the cycle the tail will be attached and the number of possible choices of is l
e)
then it remains to choose the order in which the n-l elements of the tail will be attached to the cycle . then the no of possible choices is given by (n - l)!.

the step (a) corresponds to a splitting according to the length l of the cycle After l has been chosen we can apply the product rule to step (b) through (e) summing up all these the number of graphs is given by

      ∑_(l=3)^(n-1)▒〖(n¦l).(l!/2l).l.(n-l)!.〗

on simplifying this binomial expression we get

∑_(l=3)^(n-1)▒〖(n!/2)=(n-3)n!/2.〗
so this is the possible solution of this problem