1 votes 1 votes Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$ Graph Theory nielit2017dec-scientistb discrete-mathematics graph-theory graph-coloring + – admin asked Mar 30, 2020 retagged Oct 23, 2020 by Krithiga2101 admin 3.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply yuyutsu commented Jun 24, 2022 reply Follow Share Ok nx is fine. Only when we partition the vertex set into three disjoint non empty sets with x as each of their cardinality. But no where in the question is it supposed that it should be the case, that all the vertex partitions need to have the same cardinality. How do we assume this? Just on the basis of the indication that n=3x? @GO Classes sir? 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes n=3*x and chromatic number 3.So we can partition the vertices into 3 sets let say R,B,Y.Now each set will contain n/3 vertices and it is given n/3=x so we can say each set will contain x vertices. Let the partition R contains the vertices which are colored by red. Let the partition B contains the vertices which are colored by blue. Let the partition Y contains the vertices which are colored by yellow. So according to the definition of chromatic number there will be no edges between any two vertices of the partition set R. Each vertex of R can be connected with maximum x vertices of set B and x vertices of set Y. So the maximum number of edges for each vertex of set R is x+x=2x Total maximum number of edges due to vertices of set R is = 2x*x=2x^2. So according to the definition of chromatic number there will be no edges between any two vertices of the partition set B. Each vertex of B can be connected with maximum x vertices of set Y. Total maximum number of edges due to vertices of set R is = x*x=x^2. Total maximum number of edges of this undirected graph can be = 2x^2+x^2=3x^2=3x*x=nx. debasish paramanik answered Oct 24, 2020 debasish paramanik comment Share Follow See 1 comment See all 1 1 comment reply jayesh_varma commented Mar 30, 2023 reply Follow Share when we partition in equal sets, we can maximize number of edges btw:nice explanation 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes As chromatic no=3, divide vertices into 3 partitions so that there will be no edges in 1 particular partition. x=1,n=3 so maximum edge=3 x=2,n=6,maxm edge=12 option c satisfies vivekgatecs2020 answered Mar 8, 2020 vivekgatecs2020 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes answer is D Akshay Koli 4 answered Dec 19, 2017 Akshay Koli 4 comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Anu007 commented Dec 19, 2017 reply Follow Share Try with 3 vertex (x= 1) edges= 3*1 =3, and 6 vertex(x=2) = 6*2= 12 edges( all edges are bidirection ) Bdw in previous image if you count edges then that will be 13 .(use common sence ) 1 votes 1 votes Akshay Koli 4 commented Dec 19, 2017 reply Follow Share there is a edge between R-R, how can you assign same color to both. 0 votes 0 votes Anu007 commented Dec 19, 2017 reply Follow Share did you count number of edges in previous image. your answer is wrong . 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Option C can be checked with x=2, so it will be a 6 vertex graph same as the graph shown in the comment by @Anu007 !KARAN answered Mar 7, 2020 !KARAN comment Share Follow See all 0 reply Please log in or register to add a comment.