The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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
asked in Graph Theory by Active (1.2k points) | 41 views
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 )

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 !

Please log in or register to answer this question.

Related questions

+3 votes
0 answers
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,587 questions
54,197 answers
71,151 users