DSA-Test 3-Question 5

Question

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

Comments

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 )

---

THANKS :)

---

Can you please explain why Option(i) is false.Why minimum edges in a cycle is 3?

---

given that it is tri-pertite.

let first partition have vertex 'A' , second partition have vertex 'B' , and third partition have vertex 'C' ,

smallest cycle can be possible as A-B-C-A ===> Have 3 edges only !