Find the number of graphs


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.


Given n>=4, then the process of assembling this graph with required properties are as follows
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.
we choose the l vertices which form the cycles which can be done in (n`)ways.
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).
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
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


on simplifying this binomial expression we get

so this is the possible solution of this problem