NIELIT 2017 DEC Scientist B - Section B: 52

Question

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

• A. $n(n-1)/2$
• B. $n^{n-2}$
• C. $nx$
• D. $n$

Comments

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?

Answer 1

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.

Comments

when we partition in equal sets, we can maximize number of edges

btw:nice explanation

Answer 2

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

Answer 3

answer is D

Comments

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 )

---

there is a edge between R-R, how can you assign same color to both.

---

did you count number of edges in previous image.

your answer is wrong .

Answer 4

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