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.

# Find the number of graphs

**Harsha_1997**#1

**APU**#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