retagged ago by
2,128 views
0 votes
0 votes

​​​The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE?

  1. $G$ contains a complete subgraph with $k$ vertices
  2. $G$ contains an independent set of size at least $n/k$
  3. $G$ contains at least $k(k-1) / 2$ edges
  4. $G$ contains a vertex of degree at least $k$ 
retagged ago by

1 Answer

1 votes
1 votes

First Option is false because chromatic number 'k' not necessarily means that graph contains a clique on 'k' vertices. For example, Chromatic Number of a Cycle Graph on odd vertices is 3 but it doesn't contain any complete subgraph on 3 vertices.

Second Option is True by virtue of Pigeon-Hole Principle. If there are 'k' color classes and n vertices, then one color class size is atleast n/k. Note that, a color class is nothing but an independent set. 

Third option is True because minimum number of edges between k color classes is C(K,2) or 'k choose 2'

Fourth option is False because take a cycle graph on odd vertices, chromatic number is 3 but degree is not 3 for any vertex. Similarly, for any complete graph, degree for every vertex is n-1 but chromatic number is n

Answer:

Related questions

2 votes
2 votes
2 answers
1
Arjun asked Feb 16
2,094 views
The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.
1 votes
1 votes
3 answers
3
Arjun asked Feb 16
2,000 views
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.