44 views
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
| 44 views
+1
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 )

0
THANKS :)
0
Can you please explain why Option(i) is false.Why minimum edges in a cycle is 3?
+1
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 !

1
+1 vote
2