List of top Quantitative Aptitude Questions on Graph Theory asked in CAT

Three Englishmen and three Frenchmen each know one unique secret. Only one Englishman knows French, no Frenchman knows English. They exchange secrets via person-to-person calls so all know all secrets. What is minimum number of calls?

The network diagram shows cities A, B, C, D, E, F with arrows as permissible travel. How many distinct paths exist from A to F?

ABCDEFGH is a regular octagon. A and E are opposite vertices. A frog starts at A, may jump to adjacent vertices except E. When it reaches E, it stops. Let $a_n$ = number of distinct paths of exactly $n$ jumps ending at E. Find $a_{2n-1}$.

In each of these questions, a pair of graphs $ F(x) $ and $ F1(x) $ is given. These are composed of straight-line segments, shown as solid lines, in the domain $ x \in (-2, 2) $.
If $ F1(x) = F(x) $, choose the answer as 1; if $ F1(x) = -F(x) $, choose the answer as 2; if $ F1(x) = F(-x) $, choose the answer as 3; and if none of the above is true, choose the answer as 4.

Four cities are connected by roads as shown. In how many ways can you start at a city and come back to it without travelling the same road more than once?

In a six-node network, two nodes are connected to all the other nodes. Of the remaining four, each is connected to four nodes. What is the total number of links in the network?