Question

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is

• A. 99
• B. 23
• C. 7
• D. 4

Answer 1

The correct option is C 7

In graph G there is a directed edge between i to j where j is either i + 1 or 3i


Since minimum values is finding, so we need to make edge which have maximum difference in i and j here (99 - 33) = 66 is maximum.

So 7 edges are needed.