Question

Let Kn be such that vertices are labeled 1,2,3....n. number of simple paths between v1 and vn such that the labels on the paths are strictly increasing
a) 2^n
b) 2^n-2
c) (n-2)!
d) n!

Answer 1

Answer on Question #52428 – Math – Graph Theory

Let Kn be such that vertices are labeled 1,2,3...n. number of simple paths between v1 and vn such that the labels on the paths are strictly increasing

a) $2^n$

b) $2^n - 2$

c) $(n-2)!$

d) $n!$

Solution

$$\binom{n^2/2}{m}$$

The number of simple graphs of $n$ vertices and 0, 1, 2, ..., $n^2/2$ edges are obtained by substituting 0, 1, 2, ..., $n^2/2$ for $m$ in (A). The sum of all such numbers is the number of all simple graphs with $n$ vertices. Therefore the total number of simple, labeled graphs of $n$ vertices is

$$\binom{n^2/2}{0} + \binom{n^2/2}{1} + \binom{n^2/2}{2} + \cdots + \binom{n^2/2}{n^2} = 2^{n^2/2} = 2^n$$

Answer: a) $2^n$

www.AssignmentExpert.com