Finding paths in a graph with n vertices

Question

Let $n\ge2$ be a natural number. Consider the graph $G=(V,E)$ where $V=\{0,1,2,...,n\}$ and $E=(\{0,1\},\{0,2\},...,\{0,n\})\cup(\{1,2\},...,\{n−1,n\})\cup(\{n,1\})$

For paths, it's a sequence of (non-repeating) vertices. For cycles, we only distinguish them if they form different subgraphs.

How many paths of length $2$ are there in $G?$ How many paths of length $3$ are there in $G?$ How many cycles are there in $G?$

I can obviously draw out the first couple cases and count this, but there has to be a summation formula or something I'm missing...

Answer 1

The graph you are describing is a Wheel graph: http://en.wikipedia.org/wiki/Wheel_graph

To get the number of $P_{3}$ (a path of length $2$, which has $3$ vertices) in the graph, you consider the paths along the exterior of the graph. There are $n$ such paths, where $n = |V|$. Then you look at the interior paths (only interior edges are used) through the center vertex, which forms an arithmetic progression $\sum_{i=1}^{n-1} i$. Finally, you count paths using an exterior and an interior edge. You again get $n$ such paths.

To count cycles, you have $C_{i}$, for $i \in \{3, ..., n\}$, for $n \geq 3$.

Answer 2

Assume that $n\ge4$: smaller cases are sometimes a bit different and can be investigated individually.

Paths of length $2$ are just (directed) edges: there are $2n$ edges and allowing for the direction gives $4n$ paths.

For paths of length $3$

• without the centre vertex, choose the first vertex and the "direction of travel": $2n$ possibilities;
• starting with the centre vertex, choose the second vertex and one of its two neighbours: $2n$ possibilities;
• ending with the centre vertex: same as the previous case;
• with the centre vertex in the middle, choose the first and last vertex: they must not be the same: $n(n-1)$ possibilities.

So the total number is $n^2+5n$.

Since $n\ge4$, a cycle of length $3$ can only consist of two adjacent vertices on the "circumference", together with the centre: to look at it another way, one of the edges on the "circumference" together with the two edges joining it to the centre. There are $n$ possibilities.