search
Log In
2 votes
158 views
A quinpartite graph is a graph whose vertices can be partitioned into five
groups such that no two vertices in same group are connected via some edge.
The maximum number of edges in a quinpartite graph with 10 vertices,
where cardinalities of those five sets are given as {2,3,2,1,2}, is:
(A) 16
(B) 20
(C) 26
(D) 39
in Graph Theory 158 views

1 Answer

3 votes
 
Best answer

There are Five Groups and there is no edge between member of same group ===> it is 5-pertite graph

Maximum no.of edges possible when it is complete 5-pertite graph.

let name the as A,B,C,D,E, and their cardinalities are k,l,m,n,p respectively.

 

the members of A should form a edge with all members of other groups.

No.of Edges = k * ( l+m+n+p)

 

the members of B should form a edge with all members of other groups (for avoiding duplicates eliminate A group )

No.of Edges = l * ( m+n+p )

 

the members of C should form a edge with all members of other groups (for avoiding duplicates eliminate A and B group )

No.of Edges = m * ( n+p )

 

the members of D should form a edge with all members of other groups (for avoiding duplicates eliminate A,B,C group )

No.of Edges = n * ( p)

 

the members of E should form a edge with all members of other groups (for avoiding duplicates eliminate A,B,C,and D group )

No.of Edges = p * ( 0 )

 

Total edges = ( k * ( l+m+n+p) ) + (  l * ( m+n+p ) )  + (  m * ( n+p ) )  + ( n * ( p) ) .

 

Fix first the cardinalities of groups, then evaluate, For your question, answer is 39


selected by
0
nicely explained Thanks :)
0

Yes.Answer is (D)39.

You can refer http://faculty.kutztown.edu/rieksts/225-F-08/graphs/tripartite.html to know about a complete quintpartite graph :)

Related questions

0 votes
0 answers
1
141 views
Let T = (V, E) be a tree and let d(v) be the degree of a vertex. Consider following statements: (i) P v∈V (2 − d(v)) = 2 (ii) If T has a vertex of degree m ≥ 2, then it has at least m vertices of degree 1. (iii) P v∈V (k − d(v)) = k, for k ≥ 2 | k ∈ Z + Which of the above statements is/are ture: (A) (i) only (B) (i), (ii) only (C) (ii) and (iii) only (D) (i), (ii) and (iii) only
asked Sep 18, 2018 in Graph Theory Sandy Sharma 141 views
1 vote
1 answer
2
366 views
For which of the following scenarios does there exist a simple graph G = (V, E) satisfying the specified conditions? (A) It has 3 components 20 vertices and 16 edges. (B) It has 10 vertices, 38 edges, and more than one component. (C) It has 7 vertices, 10 edges, and more than two components. (D) It is connected and has 10 edges 5 vertices and fewer than 6 cycles.
asked Sep 18, 2018 in Graph Theory Sandy Sharma 366 views
0 votes
1 answer
3
340 views
Consider following statements: (i) Every simple graph has at least two vertices of the same degree. (ii) If u is a vertex of odd degree in a graph, then there exists a path from u to another vertex v of the graph where v also has odd degree. (iii) If there are exactly two vertices a and ... the above statements are not true? (A) (i) and (ii) only (B) (iii) only (C) (ii) only (D) None of the above
asked Sep 18, 2018 in Graph Theory Sandy Sharma 340 views
0 votes
0 answers
4
144 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) ... above statements are true: (A) (i) only (B) (iii) only (C) (ii) and (iii) only (D) (i) and (ii) only
asked Sep 18, 2018 in Graph Theory Sandy Sharma 144 views
...