9780023606922, Chapter 2, Problem 28E

Prévia do material em texto

Chapter 2, Problem 28E Step-by-step solution Step 1 of 3 A Kn is a complete graph of n vertices, such that every vertex is connected to every other vertex in the graph. Such a graph is also called clique. Now, let us find out how many simple paths can be formed in the graph Kn There are n ways of selecting the first vertex out of the n vertices, and there are 1) edges to prom to reach to the next vertex, after any of these edges is chosen, we reach another vertex, from where we can go to any other 2) vertices, and so on. Step 2 of 3 So, there are n! Ways of finding a simple path containing exactly n vertices. Similarly, if we want to find a simple path containing exactly vertices (k n), we first select the k vertices and then there can be k! Ways to find a simple path. This means that the number of simple paths in a complete graph of n vertices will be: is, (n-n)! n! +...+ (n-2)! n! + (n-1)! n! which can be re-written as follows: (n-1)!) Now, we know that, 111 Terms 2! 3! But we can approximate it for finite n terms, if n>>1, as follows: 111 e 1+ + + 2! 3! I But this value is always less than the actual value no matter how big the value of n may be. Step 3 of 3 So, we can say that n! But as n increases, the value of 1 becomes smaller and smaller and tends to zero. (n-1)! Thus, n! Now, since the number of simple paths can only be an integer, we can safely conclude this value to be: