1,868 views

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

1. $n(n-1)/2$
2. $n^{n-2}$
3. $nx$
4. $n$

### 1 comment

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?

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
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.

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.

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

by