Say we have a star graph with one central vertex, with degree $n-1$, and the other $n-1$ remaining vertices are leaves in the star graph. How many paths of length 2 are there such that we do not count the cases where 2 edges are adjacent in the diagram?

I have figured out: For example, if $n=4$ , we have one central vertex and 3 outer vertices. We would have 0 correct cases because all edges in the star graph are adjacent.

if $n = 5$, we would have 2 cases, paths of length 2 between the diagonals since they have other edges between them.

Could anyone explain how to continue counting such instances? For self-study on graph theory.


Let's count the number of paths of size 2 between two different leaves: ${n-1}\choose{2}$ and the number of paths of size 2 with adjacent edges: $n-1$.

Finally we have ${{n-1}\choose{2}} - n + 1$ paths.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.