IIT Kanpur Written Test

Question

There are 16072016 users in Facebook. A graph is formed where an edge(u,v) is defined when a male is friend to a female and vice versa. Estimate the number of simple cycle of length 1607 formed in the graph?

Answer 1

Question is nothing but asking "Is there any odd length cycle in Bipartite graph ?"

Here set A is male, set B is female and there is an edge between A and B. Now as we know there will be no odd length cycle in Bipartite graph so cycle of length 1607 (odd length) must be ZERO.

Answer 2

Here there is an edge (u,v) if a male is a friend with a female

So, cycle should be like M-F-M-F-.......

But cycle of 1607 is a odd length cycle.

which could not be formed by  M-F-M-F........ as it is a even length cycle.

Number of simple cycle should be 0

Comments

great .. 

Answer 3

This is bipartite graph and in a bipartite graph no odd cycle is possible so 0 .