# Graph

85 views
If a graph requires k different colors for its proper coloring,  then chromatic number of the graph is

(a) 1

(b) k

(c) k-1

(d) k/2
in Others

The definition of chromatic number is minimum number of different colors required to color a graph

hence chromatic number is k only

## Related questions

1
224 views
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... $x$ and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________