85 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
| 85 views

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

by Veteran (61.8k points)
selected
0
nicely explained Thanks :)
0

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

1
+1 vote
2
3
4
5
6
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}