Consider following statements about tripartite graph, i.e. TPG, which contains three subsets of vertices of graph as A,B and C: (i) Minimum number of edges in a cycle in a TPG which passes through all three subsets of vertices is 6. (ii) A complete TPG can be colored with atmost 3 colors. (iii) Maximum number of edges in a TPG with n vertices is n 2 3 . Which of the above statements are true: (A) (i) only (B) (iii) only (C) (ii) and (iii) only (D) (i) and (ii) only
Maximum number of edges in a TPG with n vertices is n 2 3 .
what is n 2 3 means?
correct that sentence.
I. False ( minimum edges in a cycle = 3 )
II. True ( Actually it is equal to 3 )
III. Maximum no.of edges = no.of vertices in A * no.of vertices in B * no.of vertices in C ( This will be maximum when almost A=B=C )
@