Redirected
retagged by
2,996 views
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

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

4 Answers

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.
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
0 votes
0 votes
answer is D
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

 

Answer:

Related questions

0 votes
0 votes
1 answer
1
admin asked Mar 30, 2020
2,319 views
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to:$15$$30$$56$$...
0 votes
0 votes
1 answer
2
admin asked Mar 30, 2020
2,658 views
In how many ways $8$ girls and $8$ boys can sit around a circular table so that no two boys sit together?$(7!)^2$$(8!)^2$$7!8!$$15!$
1 votes
1 votes
4 answers
4
admin asked Mar 30, 2020
943 views
The number of integers between $1$ and $500$(both inclusive) that are divisible by $3$ or $5$ or $7$ is _________.$269$$270$$271$$272$