[Math] Determine the number of paths of length 2 in a complete graph of n nodes

algorithmsasymptoticsgraph theory

Question: Determine the number of paths of length 2 in a completed graph of n nodes. Give your answer in Big-O notation as a function of n

So I started working on this problem however I know im doing something wrong

So a complete graph is when every pair of distinct vertices is connected by a unique edge.

patterns
So i started drawing graphs with different number of nodes and found the number of paths depending on the number of nodes and across this equation for n number of nodes Kn = n(n-2)/2. Now the path length has to be two so would the equation be (n(n-2)/2)/2. Im confused someone please help me out.

Thanks

Best Answer

Given three vertices there are three paths of length two on those three vertices. The answer is hence $3\binom{n}{3}$

Related Question